Cellular automata: descriptional complexity and decidability

DOI10.1007/978-3-319-73216-9_6MaRDI QIDQ5112166zbMATH OpenOpenAlexFDO

Authors Martin Kutrib, Andreas Malcher

Publication date 28 May 2020

Published in Reversibility and Universality (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-73216-9_6

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Cellular automata (computational aspects) (68Q80)

Recommendations

• scientific article; zbMATH DE number 2068878
• The size of one-way cellular automata
• Decidability and undecidability in cellular automata
• Linear cellular automata and decidability
• Reversibility and surjectivity problems of cellular automata

Cites work

• A survey on operational state complexity
• An introduction to Kolmogorov complexity and its applications
• Cellular automata -- a computational point of view
• Cellular automata with limited inter-cell bandwidth
• Cellular automata. A parallel model. Papers from the Spring School of Theoretical Computer Science, Saissac, France, 1996
• Cellular devices and unary languages
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity -- an introductory survey
• Fast one-way cellular automata.
• Handbook of Natural Computing
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 2068878 (Why is no real title available?)
• scientific article; zbMATH DE number 2113947 (Why is no real title available?)
• Input-Driven Pushdown Automata with Limited Nondeterminism
• Iterative arrays with set storage
• Iterative arrays with small time bounds
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the computational capacity of parallel communicating finite automata
• On the State Complexity of Operations on Two-Way Finite Automata
• On two-way communication in cellular automata with a fixed number of cells
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Real-time language recognition by one-way and two-way cellular automata
• Returning parallel communicating finite automata with communication bounds: hierarchies, decidabilities, and undecidabilities
• Reversible computing and cellular automata -- a survey
• Signals in one-dimensional cellular automata
• Some undecidable problems for parallel communicating finite automata systems
• State complexity of regular languages
• Stateless one-way multi-head finite automata with pebbles
• Sublinearly space bounded iterative arrays
• The size impact of little iterative array resources
• The size of one-way cellular automata
• The state complexities of some basic operations on regular languages
• Theory of cellular automata: a survey
• Undecidability and hierarchy results for parallel communicating finite automata

Cited in

(10)

• The size of one-way cellular automata
• scientific article; zbMATH DE number 17562 (Why is no real title available?)
• scientific article; zbMATH DE number 2068878 (Why is no real title available?)
• Computational complexity of the stability problem for elementary cellular automata
• The complexity of limit languages of cellular automata: An example
• A tutorial on elementary cellular automata with fully asynchronous updating. General properties and convergence dynamics
• Hierarchies and undecidability results for iterative arrays with sparse communication
• Real-time pattern generation by one-dimensional cellular automata
• Cellular automata: from black-and-white to high gloss color
• State-limited inductive inference of cellular automata

This page was built for publication: Cellular automata: descriptional complexity and decidability

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