The complexity of reversible cellular automata

DOI10.1016/j.tcs.2004.06.011zbMath1071.68069OpenAlexW2070163745MaRDI QIDQ1884853

Klaus Sutner

Publication date: 27 October 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.06.011

zbMATH Keywords

Cellular automataIntermediate degrees

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Dynamical aspects of cellular automata (37B15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (6)

Inverse rules of ECA with rule number 150 ⋮ Hybrid one-dimensional reversible cellular automata are regular ⋮ The reachability problem for finite cellular automata ⋮ New aspects of symmetry of elementary cellular automata ⋮ Characterization of reversible intermediate boundary cellular automata ⋮ Computational classification of cellular automata

Cites Work

• Classifying circular cellular automata
• Invertible cellular automata: A review
• Computation-universality of one-dimensional one-way reversible cellular automata
• Cellular automata and intermediate degrees.
• Automata Studies. (AM-34)
• Time/Space Trade-Offs for Reversible Computation
• Logical Reversibility of Computation
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The complexity of reversible cellular automata