Cellular Automata: Descriptional Complexity and Decidability

DOI10.1007/978-3-319-73216-9_6zbMath1434.68316OpenAlexW2788950217MaRDI QIDQ5112166

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

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

Related Items (2)

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

Cites Work

• Cellular automata with limited inter-cell bandwidth
• Descriptional and computational complexity of finite automata -- a survey
• Reversible computing and cellular automata -- a survey
• Signals in one-dimensional cellular automata
• The state complexities of some basic operations on regular languages
• Fast one-way cellular automata.
• Some undecidable problems for parallel communicating finite automata systems
• On two-way communication in cellular automata with a fixed number of cells
• Theory of cellular automata: a survey
• Returning Parallel Communicating Finite Automata with Communication Bounds: Hierarchies, Decidabilities, and Undecidabilities
• UNDECIDABILITY AND HIERARCHY RESULTS FOR PARALLEL COMMUNICATING FINITE AUTOMATA
• ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA
• Input-Driven Pushdown Automata with Limited Nondeterminism
• PARALLEL FINITE AUTOMATA SYSTEMS COMMUNICATING BY STATES
• SUBLINEARLY SPACE BOUNDED ITERATIVE ARRAYS
• Handbook of Natural Computing
• NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
• On the State Complexity of Operations on Two-Way Finite Automata
• STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Cellular Automata: Descriptional Complexity and Decidability