2017/05/31 by Kitti Gelle, Szabolcs Iván
Computer Science · Engineering · Mathematics · #Advanced Memory and Neural Computing #Algorithm #Artificial intelligence #Automaton #Büchi automaton #Class (philosophy) #Computation #Computer science #Congruence (geometry) #Deterministic automaton #Discrete mathematics #Ferroelectric and Negative Capacitance Devices #Finitely-generated abelian group #Mathematics #Point (geometry) #Quantum Computing Algorithms and Architecture #Regular language #Theoretical computer science #cs.FL
paper · pdf · doi:10.4204/eptcs.252.13
published as EPTCS 252, 2017, pp. 114-127 · In Proceedings AFL 2017, arXiv:1708.06226
openalex publication_date 2017/08/21 · arxiv created 2017/08/22 · arxiv updated 2017/08/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Reversible forms of computations are often interesting from an energy efficiency point of view. When the computation device in question is an automaton, it is known that the minimal reversible automaton recognizing a given language is not necessarily unique, moreover, there are languages having arbitrarily large reversible recognizers possessing no nontrivial reversible congruence. However, the exact characterization of this class of languages was open. In this paper we give a forbidden pattern capturing the reversible regular languages having only finitely many reduced reversible automata, allowing an efficient (NL) decision procedure.