Published by the Department of Computer Science, The University of Chicago.
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.
We also obtain an equality which relates varieties of ordered
J-trivial monoids with the variety of
Submitted December 17, 2007, revised version submitted June 15 2010, published June 21, 2010.