Complexity of one-way cellular automata

DOI10.1007/978-3-319-18812-6_1MaRDI QIDQ5501608zbMATH OpenOpenAlexFDO

Authors Martin Kutrib

Publication date 4 August 2015

Published in Cellular Automata and Discrete Complex Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-18812-6_1

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25) Cellular automata (computational aspects) (68Q80)

Recommendations

• On time computability of functions in one-way cellular automata
• On one-way one-bit O (one)-message cellular automata
• Fast one-way cellular automata.
• scientific article; zbMATH DE number 1222612
• scientific article; zbMATH DE number 522866

Cites work

• Cellular automata -- a computational point of view
• Cellular devices and unary languages
• Constructible functions in cellular automata and their applications to hierarchy results
• Deterministic one-way simulation of two-way real-time cellular automata and its related problems
• Fast one-way cellular automata.
• scientific article; zbMATH DE number 2086248 (Why is no real title available?)
• scientific article; zbMATH DE number 1222612 (Why is no real title available?)
• scientific article; zbMATH DE number 1886323 (Why is no real title available?)
• scientific article; zbMATH DE number 1886333 (Why is no real title available?)
• scientific article; zbMATH DE number 2113950 (Why is no real title available?)
• scientific article; zbMATH DE number 1418341 (Why is no real title available?)
• Language not recognizable in real time by one-way cellular automata
• Non-deterministic cellular automata and languages
• On One-Way Cellular Arrays
• On real time one-way cellular array
• On real-time cellular automata and trellis automata
• On time computability of functions in one-way cellular automata
• One-way bounded cellular automata
• Quasi-realtime languages
• Real-time computations with restricted nondeterminism
• Real-time language recognition by one-dimensional cellular automata
• Relationships between nondeterministic and deterministic tape complexities
• Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
• Signals in one-dimensional cellular automata

Cited in

(12)

• On time computability of functions in one-way cellular automata
• One-way cellular automata on Cayley graphs
• Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
• Iterative arrays with self-verifying communication cell
• The size of one-way cellular automata
• scientific article; zbMATH DE number 522866 (Why is no real title available?)
• scientific article; zbMATH DE number 1834667 (Why is no real title available?)
• Shrinking One-Way Cellular Automata
• Iterative arrays with self-verifying communication cell
• Associating parallel automata network dynamics and strictly one-way cellular automata
• A sequential solution to the density classification task using an intermediate alphabet
• Low complexity classes of multidimensional cellular automata

This page was built for publication: Complexity of one-way cellular automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501608)