6533b7d1fe1ef96bd125cd3d

RESEARCH PRODUCT

Varieties Generated by Certain Models of Reversible Finite Automata

Jean-eric PinMarats Golovkins

subject

finite monoidNested word[INFO.INFO-OH]Computer Science [cs]/Other [cs.OH]Quantum automaton0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computer Science::Computational Complexityω-automatonregular language01 natural sciences[MATH.MATH-GR]Mathematics [math]/Group Theory [math.GR]Regular languageQuantum finite automata0101 mathematicsReversible automatonMathematicsDiscrete mathematicsFinite-state machine010102 general mathematicsNonlinear Sciences::Cellular Automata and Lattice GasesMR 68Q70AutomatonClosure (mathematics)010201 computation theory & mathematicsAutomata theoryComputer Science::Formal Languages and Automata Theory

description

Reversible finite automata with halting states (RFA) were first considered by Ambainis and Freivalds to facilitate the research of Kondacs-Watrous quantum finite automata. In this paper we consider some of the algebraic properties of RFA, namely the varieties these automata generate. Consequently, we obtain a characterization of the boolean closure of the classes of languages recognized by these models.

yearjournalcountryeditionlanguage
2006-01-01
https://doi.org/10.1007/11809678_11