Computing Issues of Asynchronous CA

DOI10.3233/FI-2012-755zbMath1283.68226OpenAlexW1608518359MaRDI QIDQ4902304

Alberto Dennunzio, Luca Manzoni, Enrico Formenti

Publication date: 14 January 2013

Published in: Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3233/fi-2012-755

zbMATH Keywords

computational complexityTuring machinesasynchronous cellular automataTuring universality

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (19)

\(m\)-asynchronous cellular automata: from fairness to quasi-fairness ⋮ Computation of functions on \(n\) bits by asynchronous clocking of cellular automata ⋮ Synchronous cellular automata-based scheduler initialized by heuristic and modeled by a pseudo-linear neighborhood ⋮ Chaos and ergodicity are decidable for linear cellular automata over \((\mathbb{Z}/m\mathbb{Z})^n\) ⋮ Multidimensional cellular automata: closing property, quasi-expansivity, and (un)decidability issues ⋮ 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 ⋮ A tutorial on elementary cellular automata with fully asynchronous updating. General properties and convergence dynamics ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications ⋮ CLOUDS IN THE BASINS OF FULLY ASYNCHRONOUS CELLULAR AUTOMATA ⋮ Fixing monotone Boolean networks asynchronously ⋮ On the dynamical behaviour of linear higher-order cellular automata and its decidability ⋮ Three research directions in non-uniform cellular automata ⋮ Swarm Intelligence ⋮ Computational complexity of finite asynchronous cellular automata ⋮ Supercritical probabilistic cellular automata: how effective is the synchronous updating? ⋮ Dynamical behavior of additive cellular automata over finite abelian groups ⋮ Turing-completeness of asynchronous non-camouflage cellular automata ⋮ Additive Cellular Automata Over Finite Abelian Groups: Topological and Measure Theoretic Properties

This page was built for publication: Computing Issues of Asynchronous CA