A lower bound for reversible automata

Pierre-Cyrille Héam

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2000)

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

How to cite

top

Héam, Pierre-Cyrille. "A lower bound for reversible automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 34.5 (2000): 331-341. <http://eudml.org/doc/92638>.

@article{Héam2000,
author = {Héam, Pierre-Cyrille},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {reversible automaton; finite automaton},
language = {eng},
number = {5},
pages = {331-341},
publisher = {EDP-Sciences},
title = {A lower bound for reversible automata},
url = {http://eudml.org/doc/92638},
volume = {34},
year = {2000},
}

TY - JOUR
AU - Héam, Pierre-Cyrille
TI - A lower bound for reversible automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2000
PB - EDP-Sciences
VL - 34
IS - 5
SP - 331
EP - 341
LA - eng
KW - reversible automaton; finite automaton
UR - http://eudml.org/doc/92638
ER -

References

top
  1. [1] D. Angluin, Inference of reversible languages. J. ACM 29 (1982) 741-765. Zbl0485.68066MR666776
  2. [2] J. Berstel, Transductions and Context-Free Languages. B.G. Teubner, Stuttgart (1979). Zbl0424.68040MR549481
  3. [3] M. Hall, A topology for free groups and related groups. Ann. of Math. 52 (1950). Zbl0041.36210MR36767
  4. [4] T. Hall, Biprefix codes, inverse semigroups and syntactic monoids of injective automata. Theoret. Comput. Sci. 32 (1984) 201-213. Zbl0567.68047MR761168
  5. [5] B. Herwig and D. Lascar, Extending partial automorphisms and the profinite topology on free groups. Trans. Amer. Math. Soc. 352 (2000) 1985-2021. Zbl0947.20018MR1621745
  6. [6] S. Margolis and J. Meakin, Inverse monoids, trees, and context-free languages. Trans. Amer. Math. Soc. 335 (1993) 259-276. Zbl0795.20043MR1073775
  7. [7] S. Margolis, M. Sapir and P. Weil, Closed subgroups in pro-V topologies and the extension problem for inverse automata. Preprint (1998). Zbl1027.20036MR1850210
  8. [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. Zbl0566.68061MR784261
  9. [9] J.-E. Pin, Topologies for the free monoid. J. Algebra 137 (1991). Zbl0739.20032MR1094245
  10. [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. MR1253368
  11. [11] P.V. Silva, On free inverse monoid languages. RAIRO: Theoret. Informatics Appl. 30 (1996) 349-378. Zbl0867.68074MR1427939
  12. [12] B. Steinberg, Finite state automata: A geometric approach. Technical Report, Univ. of Porto (1999). Zbl0980.20067
  13. [13] B. Steinberg, Inverse automata and profinite topologies on a free group. Preprint (1999). MR1874549

NotesEmbed ?

top

You must be logged in to post comments.