# A Lower Bound For Reversible Automata

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 34, Issue: 5, page 331-341
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topHéam, Pierre-Cyrille. "A Lower Bound For Reversible Automata." RAIRO - Theoretical Informatics and Applications 34.5 (2010): 331-341. <http://eudml.org/doc/221965>.

@article{Héam2010,

abstract = {
A reversible automaton is a finite automaton in which each
letter induces a partial one-to-one map from the set of states into
itself. We solve the following problem proposed by Pin. Given an
alphabet A, does there exist a sequence of languages Kn on A
which can be accepted by a reversible automaton, and such that the
number of states of the minimal automaton of Kn is in O(n), while
the minimal number of states of a reversible automaton accepting
Kn is in O(ρn) for some ρ > 1? We give such an example with
$\rho=\left(\frac\{9\}\{8\}\right)^\{\frac\{1\}\{12\}\}$.
},

author = {Héam, Pierre-Cyrille},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Automata; formal languages; reversible automata; reversible automaton; finite automaton},

language = {eng},

month = {3},

number = {5},

pages = {331-341},

publisher = {EDP Sciences},

title = {A Lower Bound For Reversible Automata},

url = {http://eudml.org/doc/221965},

volume = {34},

year = {2010},

}

TY - JOUR

AU - Héam, Pierre-Cyrille

TI - A Lower Bound For Reversible Automata

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 34

IS - 5

SP - 331

EP - 341

AB -
A reversible automaton is a finite automaton in which each
letter induces a partial one-to-one map from the set of states into
itself. We solve the following problem proposed by Pin. Given an
alphabet A, does there exist a sequence of languages Kn on A
which can be accepted by a reversible automaton, and such that the
number of states of the minimal automaton of Kn is in O(n), while
the minimal number of states of a reversible automaton accepting
Kn is in O(ρn) for some ρ > 1? We give such an example with
$\rho=\left(\frac{9}{8}\right)^{\frac{1}{12}}$.

LA - eng

KW - Automata; formal languages; reversible automata; reversible automaton; finite automaton

UR - http://eudml.org/doc/221965

ER -

## References

top- D. Angluin, Inference of reversible languages. J. ACM29 (1982) 741-765.
- J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979).
- M. Hall, A topology for free groups and related groups. Ann. of Math.52 (1950).
- T. Hall, Biprefix codes, inverse semigroups and syntactic monoids of injective automata. Theoret. Comput. Sci.32 (1984) 201-213.
- B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups. Trans. Amer. Math. Soc.352 (2000) 1985-2021.
- S. Margolis and J. Meakin, Inverse monoids, trees, and context-free languages. Trans. Amer. Math. Soc.335 (1993) 259-276.
- S. Margolis, M. Sapir and P. Weil, Closed subgroups in pro-Vtopologies and the extension problem for inverse automata. Preprint (1998).
- S.W Margolis and J.-E. Pin, Languages and inverse semigroups, edited by J. Paredaens, Automata, Languages and Programming, 11th Colloquium. Antwerp, Belgium. Springer-Verlag, Lecture Notes in Comput. Sci.172 (1984) 337-346.
- J.-E. Pin, Topologies for the free monoid. J. Algebra137 (1991).
- J.-E. Pin, On reversible automata, edited by I. Simon, in Proc. of Latin American Symposium on Theoretical Informatics (LATIN '92). Springer, Berlin, Lecture Notes in Comput. Sci. 583 (1992) 401-416; A preliminary version appeared in the Proceedings of ICALP'87, Lecture Notes in Comput. Sci. 267.
- P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl.30 (1996) 349-378.
- B. Steinberg, Finite state automata: A geometric approach. Technical Report, Univ. of Porto (1999).
- B. Steinberg, Inverse automata and profinite topologies on a free group. Preprint (1999).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.