Computational complexity of finite asynchronous cellular automata

DOI10.1016/j.tcs.2015.12.003zbMath1359.68207OpenAlexW2212525746WikidataQ57518141 ScholiaQ57518141MaRDI QIDQ517039

Antonio E. Porreca, Giancarlo Mauri, Luca Manzoni, Enrico Formenti, Alberto Dennunzio

Publication date: 16 March 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.12.003

zbMATH Keywords

computational complexitynatural computingasynchronous cellular automata

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (11)

Complexity of the dynamics of reaction systems ⋮ Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption ⋮ Building squares with optimal state complexity in restricted active self-assembly ⋮ The impact of alphabet size on pattern complexity of maxmin-\( \omega\) cellular automata ⋮ Topological dynamics of nondeterministic cellular automata ⋮ On the complexity of the stability problem of binary freezing totalistic cellular automata ⋮ Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations ⋮ On the dynamical behaviour of linear higher-order cellular automata and its decidability ⋮ Turing-completeness of asynchronous non-camouflage cellular automata ⋮ A spectral outlook on the elementary cellular automata with cyclic configurations and block-sequential asynchronous updates ⋮ On the impact of treewidth in the computational complexity of freezing dynamics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• \(m\)-asynchronous cellular automata: from fairness to quasi-fairness
• Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
• Local rule distributions, language complexity and non-uniform cellular automata
• Non-uniform cellular automata: classes, dynamics, and decidability
• Conservation of some dynamical properties for operations on cellular automata
• The polynomial-time hierarchy
• Theory of cellular automata: a survey
• On the computational complexity of finite cellular automata
• Surjective multidimensional cellular automata are non-wandering: a combinatorial proof
• Fully asynchronous behavior of double-quiescent elementary cellular automata
• Asynchronous cellular automata and dynamical properties
• Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
• Periodicity and Immortality in Reversible Computing
• Nondeterministic Space is Closed under Complementation
• Computing Issues of Asynchronous CA

This page was built for publication: Computational complexity of finite asynchronous cellular automata