Computational complexity of finite asynchronous cellular automata
From MaRDI portal
Publication:517039
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
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
