A lower bound for reversible automata
Héam, Pierre-Cyrille
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 331-341 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 2000-01-01
@article{ITA_2000__34_5_331_0,
     author = {H\'eam, Pierre-Cyrille},
     title = {A lower bound for reversible automata},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {331-341},
     mrnumber = {1829230},
     zbl = {0987.68043},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_5_331_0}
}

Héam, Pierre-Cyrille. A lower bound for reversible automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 331-341. http://gdmltest.u-ga.fr/item/ITA_2000__34_5_331_0/

[1] D. Angluin, Inference of reversible languages. J. ACM 29 (1982) 741-765. | MR 666776 | Zbl 0485.68066

[2] J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979). | MR 549481 | Zbl 0424.68040

[3] M. Hall, A topology for free groups and related groups. Ann. of Math. 52 (1950). | MR 36767 | Zbl 0041.36210

[4] T. Hall, Biprefix codes, inverse semigroups and syntactic monoids of injective automata. Theoret. Comput. Sci. 32 (1984) 201-213. | MR 761168 | Zbl 0567.68047

[5] B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups. Trans. Amer. Math. Soc. 352 (2000) 1985-2021. | MR 1621745 | Zbl 0947.20018

[6] S. Margolis and J. Meakin, Inverse monoids, trees, and context-free languages. Trans. Amer. Math. Soc. 335 (1993) 259-276. | MR 1073775 | Zbl 0795.20043

[7] S. Margolis, M. Sapir and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata. Preprint (1998). | MR 1850210

[8] 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. | MR 784261 | Zbl 0566.68061

[9] J.-E. Pin, Topologies for the free monoid. J. Algebra 137 (1991). | MR 1094245 | Zbl 0739.20032

[10] 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. | MR 1253368

[11] P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl. 30 (1996) 349-378. | Numdam | MR 1427939 | Zbl 0867.68074

[12] B. Steinberg, Finite state automata: A geometric approach. Technical Report, Univ. of Porto (1999).

[13] B. Steinberg, Inverse automata and profinite topologies on a free group. Preprint (1999). | MR 1874549