Published by the Department of Computer Science, The University of Chicago.

Abstract

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 R-trivial monoids.

• The article: PDF (488,365 bytes)
• Source materials: ZIP (301,547 byes)
• Self citation in BIBTeX (326 bytes)
• Original version (pre-June 2010): PDF (201,987)

Submitted December 17, 2007, revised version submitted June 15 2010, published June 21, 2010.

© 2010 Marats Golovkins and Jean-Eric Pin
Licensed under a Creative Commons Attribution License

Volume 2010, Article 1

Volume 2009

Published articles