The complexity of reversible cellular automata

DOI10.1016/J.TCS.2004.06.011MaRDI QIDQ1884853zbMATH OpenOpenAlexFDO

Authors K. 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

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

Recommendations

• The structure of reversible one-dimensional cellular automata
• On the structure of the set of reversible cellular automata
• Cellular automata and intermediate degrees.
• Cellular automata reversible over limit set
• Reversibility and surjectivity problems of cellular automata

Cites work

• scientific article; zbMATH DE number 1818513 (Why is no real title available?)
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 4211534 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 2113941 (Why is no real title available?)
• scientific article; zbMATH DE number 3305030 (Why is no real title available?)
• Automata Studies. (AM-34)
• Cellular automata and intermediate degrees.
• Classifying circular cellular automata
• Computation-universality of one-dimensional one-way reversible cellular automata
• Invertible cellular automata: A review
• Logical Reversibility of Computation
• Time/Space Trade-Offs for Reversible Computation

Cited in

(15)

• scientific article; zbMATH DE number 7179993 (Why is no real title available?)
• Characterization of reversible intermediate boundary cellular automata
• scientific article; zbMATH DE number 2013811 (Why is no real title available?)
• Reversibility of linear cellular automata
• ON THE REVERSIBILITY OF 150 WOLFRAM CELLULAR AUTOMATA
• Reverse complexity
• Hybrid one-dimensional reversible cellular automata are regular
• Cellular automata and intermediate degrees.
• scientific article; zbMATH DE number 176951 (Why is no real title available?)
• Trace complexity of chaotic reversible cellular automata
• Inverse rules of ECA with rule number 150
• Computational classification of cellular automata
• New aspects of symmetry of elementary cellular automata
• scientific article; zbMATH DE number 1741020 (Why is no real title available?)
• The reachability problem for finite cellular automata

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

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