Résumé : Cet article est la version
complète d'un article publié dans COCOON 2006. 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. On obtient également une égalité qui
relie les variétés des monoïdes ordonnés
J-triviaux aux monoïdes R-triviaux.
Abstract : This is the full version of an
article published in COCOON 2006.@ 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.