Equidivisible Kleene monoids and the Elgot-Mezei theorem. (English) Zbl 0685.20048

Let M be a monoid, \(A^*\) and \(M^*\) stand for the varying free monoids. A monoid M satisfies the Elgot-Mezei theorem if for any rational relations f: \(A^*\to M\) and g: \(M\to C^*\) the composition gf is rational too. The main result in the paper is that equidivisible Kleene monoids satisfy this theorem. The proof and some additional comments are supplied.
Reviewer: K.Peeva


20M35 Semigroups in automata theory, linguistics, etc.
20M05 Free semigroups, generators and relations, word problems
Full Text: DOI EuDML


[1] Amar, V. and G. Putzolu,Generalizations of Regular Events, Information and Control 8 (1965), 56–63. · Zbl 0236.94041
[2] Berstel, J.,Transductions and Context-Free Languages, Stuttgart: 1979. · Zbl 0424.68040
[3] Clifford, A. H. and G. B. Preston,The Algebraic Theory of Semigroups, Volume 1, Providence: 1961. · Zbl 0111.03403
[4] Eilenberg, S.,Automata,Languages,and Machines, Volume A, New York: 1974, 256–257.
[5] Elgot, C. C. and J. E. Mezei,On Relations Defined by Generalized Finite Automata, IBM Journal of Research and Development 9 (1965), 47–68. · Zbl 0135.00704
[6] Johnson, J. H.Do Rational Equivalence Relations Have Rational Cross-Sections?, ICALP 85, LNCS 194, Berlin: 1985, 300–309. · Zbl 0571.68069
[7] Kleene, S. C.,Representations of Events in Nerve Nets and Finite Automata inAutomata Studies, C. E. Shannon and J. McCarthy (ed.), Princeton: 1956, 3–41.
[8] Lallement, G.,Semigroups and Combinatorial Applications New York: 1979.
[9] McKnight Jr., J. D.Kleene Quotient Theorems, Pacific Journal of Mathematics 14 (1964), 1343–1352. · Zbl 0144.01201
[10] McKnight Jr., J. D. and A. J. Storey,Equidivisible Semigroups, Journal of Algebra 12 (1969), 24–48. · Zbl 0192.34504
[11] Reutenauer, C.:Sur les Semi-Groupes Vérifiant le Théorème de Kleene, RAIRO Informatique Théorique, 19 (1985), 281–291. · Zbl 0575.20055
[12] Rupert, C. P.,Certain Rational Sets in Formal Language Theory, dissertation, The Pennsylvania State University: 1988.
[13] Sakarovitch, J.,Easy Multiplications I:The Realm of Kleene’s Theorem, Information and Computation 74 (1987), 173–197. · Zbl 0642.20043
[14] Sakarovitch, J.,On Regular Trace Languages, Theoretical Computer Science 52 (1987), 59–75. · Zbl 0634.68076
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.