Chicago Journal of Theoretical Computer Science

Volume 2010

Article 2

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

Varieties Generated by Certain Models of Reversible Finite Automata

Marats Golovkins
Faculty of Computing
University of Latvia
Raina Bulv. 29 Riga LV-1459, Latvia

Jean-Eric Pin
LIAFA, Universite' Paris Diderot and CNRS
2 Place Jussieu, 75205 Paris, France

June 20, 2010

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.

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

DOI: 10.4086/cjtcs.2010.002

[] Volume 2010, Article 1
[back] Volume 2009 [back] Published articles
[CJCTS home]