The complexity of iterated reversible computation

DOI10.46298/THEORETICS.23.10MaRDI QIDQ6566596zbMATH OpenFDO

Authors David Eppstein

Publication date 3 July 2024

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.23.10

zbMATH Keywords

cellular automatacircuit complexityreversible computinginterval exchange transformationsreversible cellular automata

Mathematics Subject Classification ID

Computer science (68-XX)

Cites work

• scientific article; zbMATH DE number 3898247 (Why is no real title available?)
• scientific article; zbMATH DE number 1189123 (Why is no real title available?)
• scientific article; zbMATH DE number 3692653 (Why is no real title available?)
• scientific article; zbMATH DE number 176951 (Why is no real title available?)
• scientific article; zbMATH DE number 3305030 (Why is no real title available?)
• A Footnote to the Three Gaps Theorem
• A computation-universal two-dimensional 8-state triangular reversible cellular automaton
• A short note on graphs with long Thomason chains
• Complexity of some geometric and topological problems
• Computation and construction universality of reversible cellular automata
• Conservative logic
• Efficient exhaustive listings of reversible one dimensional cellular automata
• Endomorphisms and automorphisms of the shift dynamical system
• Firing squad synchronization problem in reversible cellular automata
• Hamiltonian Cycles and Uniquely Edge Colourable Graphs
• Hard tiling problems with simple tiles
• Interval exchange transformations
• Intrinsic universality of a 1-dimensional reversible cellular automaton
• Irreversibility and Heat Generation in the Computing Process
• Logical Reversibility of Computation
• Measure-Preserving Transformations and Random Processes
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On Hamiltonian Circuits
• On the complexity of the parity argument and other inefficient proofs of existence
• Period of a Discrete Cat Mapping
• Polynomial Space Counting Problems
• Quantum computational networks
• Reversible Turing Machines and Polynomial Time Reversibly Computable Functions
• Reversible computing and cellular automata -- a survey
• Reversible simulation of one-dimensional irreversible cellular automata
• Reversible space equals deterministic space
• Simple universal one-dimensional reversible cellular automata
• Tesselations with local transformations
• The General Chinese Remainder Theorem
• The complexity of Thomason's algorithm for finding a second Hamiltonian cycle
• The complexity of finding a second Hamiltonian cycle in cubic graphs
• The complexity of graph connectivity
• The mathematics of perfect shuffles
• Thomason's algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk's graphs
• Trace complexity of chaotic reversible cellular automata
• Tracing compressed curves in triangulated surfaces

Cited in

(1)

• Foundations of block-parallel automata networks

This page was built for publication: The complexity of iterated reversible computation

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