INVERSION OF 2D CELLULAR-AUTOMATA - SOME COMPLEXITY RESULTS

被引：24
作者：
DURAND, B
机构：
[1] Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon, F-69364 Lyon Cedex 07
来源：
THEORETICAL COMPUTER SCIENCE | 1994年 / 134卷 / 02期
关键词：
Decision theory;
D O I：
10.1016/0304-3975(94)90244-5
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
In this paper, we prove the co-NP-completeness of the following decision problem: ''Given a two-dimensional cellular automaton A (even with Von Neumann neighborhood), is A injective when restricted to finite configurations not greater than its length?'' In order to prove this result, we introduce two decision problems concerning, respectively, Turing machines and tilings that we prove NP-complete. Then, we present a transformation of problems concerning tilings into problems concerning cellular automata.
引用
收藏
页码：387 / 401
页数：15
相关论文
共 14 条
[1]  
Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8
[2]  
[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047
[3]  
Berger R., 1966, MEM AM MATH SOC, V66
[4]  
DURAND B, IN PRESS J COMPUT SY
[5]  
DURAND B, 1993, LECTURE NOTES COMPUT
[6]   REVERSIBILITY OF 2D CELLULAR AUTOMATA IS UNDECIDABLE [J].
KARI, J .
PHYSICA D, 1990, 45 (1-3) :379-385
[7]  
KARI J, IN PRESS J COMPUT SY
[8]  
Moore Edward Forrest, 1962, P S APPL MATH, V14, P13
[9]  
Myhill J., 1963, P AM MATH SOC, V14, P685, DOI DOI 10.2307/2034301.
[10]  
Richardson D., 1972, Journal of Computer and System Sciences, V6, P373, DOI 10.1016/S0022-0000(72)80009-6
12