Computational complexity of finite asynchronous cellular automata
DOI10.1016/J.TCS.2015.12.003zbMATH Open1359.68207DBLPjournals/tcs/DennunzioFMMP17OpenAlexW2212525746WikidataQ57518141 ScholiaQ57518141MaRDI QIDQ517039FDOQ517039
Authors: Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Giancarlo Mauri, Antonio E. Porreca 
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
Recommendations
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Cellular automata (computational aspects) (68Q80)
Cites Work
- Title not available (Why is that?)
- Theory of cellular automata: a survey
- Title not available (Why is that?)
- 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
- \(m\)-asynchronous cellular automata: from fairness to quasi-fairness
- Title not available (Why is that?)
- Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
- Nondeterministic Space is Closed under Complementation
- Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
- Local rule distributions, language complexity and non-uniform cellular automata
- Computing issues of asynchronous CA
- Non-uniform cellular automata: classes, dynamics, and decidability
- Conservation of some dynamical properties for operations on cellular automata
- The polynomial-time hierarchy
- Periodicity and Immortality in Reversible Computing
- Title not available (Why is that?)
- Limit properties of doubly quiescent \(m\)-asynchronous elementary cellular automata
- On the computational complexity of finite cellular automata
Cited In (25)
- On the reduction of computational complexity of cellular automata
- Computation of functions on \(n\) bits by asynchronous clocking of cellular automata
- The impact of alphabet size on pattern complexity of maxmin-\( \omega\) cellular automata
- Complexity-theoretic aspects of expanding cellular automata
- Reversibility of elementary cellular automata with fully asynchronous updating: an analysis of the rules with partial recurrence
- Computational aspects of asynchronous cellular automata
- Building squares with optimal state complexity in restricted active self-assembly
- Computation by asynchronously updating cellular automata
- Maximum sensitivity to update schedules of elementary cellular automata over infinite configurations
- On the complexity of asynchronous freezing cellular automata
- Complexity of the dynamics of reaction systems
- Title not available (Why is that?)
- On the complexity of the stability problem of binary freezing totalistic cellular automata
- A characterization of constant-time cellular automata computation
- Complexity of reachability problems for finite discrete dynamical systems
- Fundamentals of Computation Theory
- On the parameterized complexity of freezing dynamics
- Turing-completeness of asynchronous non-camouflage cellular automata
- Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption
- On the dynamical behaviour of linear higher-order cellular automata and its decidability
- On the computational complexity of finite 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
- Topological dynamics of nondeterministic cellular automata
- Asymptotic (a)synchronism sensitivity and complexity of elementary cellular automata
This page was built for publication: Computational complexity of finite asynchronous cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q517039)
