Computational complexity of finite asynchronous cellular automata
From MaRDI portal
Recommendations
Cites work
- scientific article; zbMATH DE number 3888913 (Why is no real title available?)
- scientific article; zbMATH DE number 4074492 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 2046045 (Why is no real title available?)
- Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata
- Asynchronous cellular automata and dynamical properties
- Computing issues of asynchronous CA
- Conservation of some dynamical properties for operations on cellular automata
- Fully asynchronous behavior of double-quiescent elementary cellular automata
- Limit properties of doubly quiescent \(m\)-asynchronous elementary cellular automata
- Local rule distributions, language complexity and non-uniform cellular automata
- Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues
- Non-uniform cellular automata: classes, dynamics, and decidability
- Nondeterministic Space is Closed under Complementation
- On the computational complexity of finite cellular automata
- Periodicity and Immortality in Reversible Computing
- Surjective multidimensional cellular automata are non-wandering: a combinatorial proof
- The polynomial-time hierarchy
- Theory of cellular automata: a survey
- m-asynchronous cellular automata: from fairness to quasi-fairness
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
- scientific article; zbMATH DE number 6257036 (Why is no real title available?)
- On the complexity of the stability problem of binary freezing totalistic cellular automata
- Complexity of reachability problems for finite discrete dynamical systems
- A characterization of constant-time cellular automata computation
- Fundamentals of Computation Theory
- Turing-completeness of asynchronous non-camouflage cellular automata
- On the parameterized complexity of freezing dynamics
- On the dynamical behaviour of linear higher-order cellular automata and its decidability
- Decidable characterizations of dynamical properties for additive cellular automata over a finite abelian group with applications to data encryption
- 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)
