Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata

DOI10.1142/s0129054122410040OpenAlexW4280559572MaRDI QIDQ6114868

Szabolcs Iván, Kitti Gelle

Publication date: 15 August 2023

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054122410040

zbMATH Keywords

descriptional complexityforbidden patternNL-completenessreversible automatonreduced reversible automatonreversible regular languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Waiting for Landauer
• Eaters of the lotus: Landauer's principle and the return of Maxwell's demon
• The connection between logical and thermodynamic irreversibility
• EXORCIST XIV: the wrath of Maxwell's demon. II: From Szilard to Landauer and beyond
• Maxwell's demon and the thermodynamics of computation
• Notes on Landauer's principle, reversible computation, and Maxwell's demon
• Reversible space equals deterministic space
• Concise representations of reversible automata
• Minimal and Reduced Reversible Automata
• Aspects of Reversibility for Classical Automata
• Reversible and Irreversible Computations of Deterministic Finite-State Devices
• Information erasure without an energy cost
• Minimal Reversible Deterministic Finite Automata
• Irreversibility and Heat Generation in the Computing Process
• Inference of Reversible Languages
• Logical Reversibility of Computation

This page was built for publication: Descriptive Complexity of Reversible Languages Having Finitely Many Reduced Automata