Résumé : Les automates finis
réversibles avec états d'arrêt ont été
introduits par Ambainis et Freivalds dans le cadre de l'étude des
automates finis quantiques de Kondacs-Watrous. Dans cet article, nous
étudions les variétés engendrées par ces
automates. On obtient en particulier une caractérisation de la
cloture booléenne de la classe des langages reconnue par ces
modèles.
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.