×

Easy multiplications. I: The realm of Kleene’s theorem. (English) Zbl 0642.20043

Author’s summary: “We study here the properties of a family of monoids, which we call the rational monoids, and which are monoids with a multiplication of low complexity. A monoid is rational if its multiplication may be described by a rational function from a free monoid into itself. The main results are that rational monoids, like finite ones, have the properties that Green’s relations \({\mathcal D}\) and \({\mathcal J}\) are equal and that Kleene’s theorem holds in rational monoids, as in free ones. Every monoid described so far, in which Kleene’s theorem holds, is a rational monoid. The closure of the family of rational monoids under Rees’ quotient, direct product, and free product is then studied. Extensions of rational monoids will be considered in a forthcoming paper.”
Reviewer: I.Peák

MSC:

20M35 Semigroups in automata theory, linguistics, etc.
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
20M05 Free semigroups, generators and relations, word problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Amar, V.; Putzolu, G., Generalizations of regular events, Inform. Contr., 8, 56-63 (1965) · Zbl 0236.94041
[2] Berstel, J., (Transductions and Context-free Languages (1979), Teubner: Teubner Stuttgart) · Zbl 0424.68040
[3] Carlitz, L., Fibonacci representations, Fibonacci Quart., 193-220 (1968) · Zbl 0167.03901
[4] Choffrut, Ch., Contribution à l’étude de quelques familles remarquables de fonctions rationnelles, (Thèse Sci. Math. (1978), University of Paris 7)
[5] Clifford, A. H.; Preston, G. B., (The Algebraic Theory of Semigroups, Vol. 1, Vol. 2 (1967), Amer. Math. Soc: Amer. Math. Soc Providence, R. I) · Zbl 0178.01203
[6] Eilenberg, S., (Automata, Languages, and Machines, Vol. A (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[7] Elgot, C. C.; Mezei, G., On relations defined by generalized finite automata, IBM J. Res. Develop., 9, 47-65 (1965) · Zbl 0135.00704
[8] Lallement, G., (Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York) · Zbl 0421.20025
[9] Magnus, W.; Karrass, A.; Solitar, D., (Combinatorial Group Theory (1966), Wiley: Wiley New York)
[10] McKnight, J. D.; Storey, A. J., Equidivisible semigroups, J. Algebra, 12, 24-48 (1968) · Zbl 0192.34504
[11] Pelletier, M., and Sakarovitch, J.; Pelletier, M., and Sakarovitch, J.
[12] Sakarovitch, J., Description des monoïdes de type fini, EIK, 17, 417-434 (1981) · Zbl 0572.20037
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.