Languages and monoids with disjunctive identity

• Autores: Gabriel Thierrin, Lila Kari
• Localización: Collectanea mathematica, ISSN 0010-0757, Vol. 46, Fasc. 1-2, 1995 (Ejemplar dedicado a: Professor Paul Dubreil (In memoriam )), págs. 97-108
• Idioma: inglés
• Enlaces
  • Texto completo
• Resumen

  • We show that the syntactic monoids of insertion-closed, deletion-closed and dipolar-closed languages are the groups. If the languages are insertion-closed and congruence simple, then their syntactic monoids are the monoids with disjunctive identity. We conclude with some properties of dipolar-closed languages.

• Referencias bibliográficas
  • A.H. Clifford and G.B. Preston, The Algebraic Theory of Semigroups, Math. Surveys Series, 1 and 2, Amer. Math. Soc. Providence 1961, 1967.
  • R. Croisot, Equivalences principales bilatères définies dans un demi-groupe, J. Math. Pures Appl. (9), 36 (1957), 373–417.
  • P. Dubreil, Contribution à la théorie des demi-groupes, Mém. Acad. Sci. Inst. France (2) 63 (1941), 52 pp.
  • M. Ito, L. Kari and G. Thierrin, Insertion and deletion closure of languages, To appear in TCS.
  • H. Jurgensen, H.J. Shyr and G. Thierrin, Monoids with disjunctive identity, Acta Mathematica Hungarica 47 (1986), 299–312.
  • L. Kari, On insertion and deletion in formal languages, Ph. D. Thesis, University of Turku 1991.
  • L. Kari, On language equations with invertible operations, Theoretical Computer Science 132 (1994), 129–150.
  • L. Kari, Insertion and deletion of words: determinism and reversibility, Lecture Notes in Computer Science 629 (1992), 315–327.
  • L. Kari, Deletion operations: closure properties, Intern. J. Computer Math. 52 (1994), 23–42.
  • G. Lallement, Semigroups and Combinatorial Applications, John Wiley, New York 1979.
  • A. Salomaa, Formal languages, Academic Press, New York, 1973.
  • H.J. Shyr, Free monoids and languages. Lecture Notes, Institute of Applied Mathematics, National Chung-Hsing University, Taichung, Taiwan...