More Decision Algorithms for Global Properties of 1D Cellular Automata

被引：0

作者：

Autran, Sebastien ^{[1
]}

Formenti, Enrico ^{[1
]}

机构：

[1] Univ Cote Azur, CNRS, 13S, Nice, France

来源：

JOURNAL OF CELLULAR AUTOMATA | 2018年 / 13卷 / 1-2期

关键词：

Decision algorithms; computational complexity; openess; closingness; surjectivity; finite configurations;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper proposes some new decision algorithms for basic properties of one-dimensional cellular automata (CA). In particular, it provides an algorithm for deciding surjectivity on finite configurations. Moreover, by using the classical decision algorithm for surjectivity and injectivity of Sutner, we provide a simple decision algorithm for openess (although its complexity is unchanged). Finally, a complete implication diagram between global properties of one-dimensional CA is provided. When possible the corresponding algorithms for one-sided CA are also given.

引用

页码：1 / 14

页数：14

共 11 条

[1]

Amoroso S., 1972, Journal of Computer and System Sciences, V6, P448, DOI 10.1016/S0022-0000(72)80013-8

[2]

Bernardi V, 2004, LECT NOTES COMPUT SC, V3153, P416

[3] Periodic points for onto cellular automata [J].

Boyle, M ;

Kitchens, B .

INDAGATIONES MATHEMATICAE-NEW SERIES, 1999, 10 (04) :483-493

[4]

Cattaneo Gianpiero, 1995, DEV LANGUAGE THEORY, P409

[5] Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues [J].

Dennunzio, Alberto ;

Formenti, Enrico ;

Weiss, Michael .

THEORETICAL COMPUTER SCIENCE, 2014, 516 :40-59

[6]

Durand B, 1999, NONL PHEN COMPL SYST, V3, P1

[7]

Durand B., 2003, Discrete Models for Complex Systems, DMCS'03, volume AB of DMTCS Proceedings, P117

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

KARI, J .

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

[9]

Kari J., 2013, P 19 INT WORKSH CELL, V1302

[10]

Kari J, 2008, LECT NOTES COMPUT SC, V5162, P419

← 1 2 →