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
Boccara, N
Fuks, H
[J]. 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
DURAND, B
[J]. 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
KARI, J
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1994, 48 (01) : 149 - 182
[9] RICE THEOREM FOR THE LIMIT-SETS OF CELLULAR-AUTOMATA
KARI, J
[J]. THEORETICAL COMPUTER SCIENCE, 1994, 127 (02) : 229 - 254
[10] MARTINEZ S, 1993, CELLULAR AUTOMATA CO

← 1 2 →