Number-conserving cellular automata I:: decidability

被引：59

作者：

Durand, B

Formenti, E

Róka, Z

机构：

[1] Lab Informat Fondamentale Marseille, F-13453 Marseille 13, France

[2] IUT Metz, LITA, F-57045 Metz, France

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 299卷 / 1-3期

关键词：

cellular automata; decidability;

D O I：

10.1016/S0304-3975(02)00534-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that definitions of number-conserving cellular automata found in literature are equivalent. A necessary and sufficient condition for cellular automata to be number-conserving is proved. Using this condition, we give a quasi-linear time algorithm to decide number-conservation. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：523 / 535

页数：13

共 17 条

[1] Cellular automaton rules conserving the number of active sites [J].

Boccara, N ;

Fuks, H .

JOURNAL OF PHYSICS A-MATHEMATICAL AND GENERAL, 1998, 31 (28) :6007-6018

[2]

BOCCARA N, 2002, IN PRESS FUND INFORM

[3]

CERVELLE J, 2000, LECT NOTES COMPUTER, V1770

[4] THE SURJECTIVITY PROBLEM FOR 2D CELLULAR-AUTOMATA [J].

DURAND, B .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 49 (03) :718-725

[5]

FORMENTI E, 2001, UNPUB NUMBER CONSERV, V2

[6]

GUTOWITZ H, 1990, CELLULAR AUTOMATA TH

[7]

Hedlund G. A., 1969, Math. systems theory, V3, P320, DOI DOI 10.1007/BF01691062

[8] REVERSIBILITY AND SUBJECTIVITY PROBLEMS OF CELLULAR-AUTOMATA [J].

KARI, J .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (01) :149-182

[9] RICE THEOREM FOR THE LIMIT-SETS OF CELLULAR-AUTOMATA [J].

KARI, J .

THEORETICAL COMPUTER SCIENCE, 1994, 127 (02) :229-254

[10]

MARTINEZ S, 1993, CELLULAR AUTOMATA CO

← 1 2 →