rational monoid

Consider a monoid M. Consider a pair (A,L) where A is a finite subset of M that generates M as a monoid, and L is a language on A (that is, a subset of the set of all strings A^∗). Let φ be the map from the free monoid A^∗ to M given by evaluating a string as a product in M. We say that L is a rational cross-section if φ induces a bijection between L and M. We say that (A,L) is a rational structure for M if in addition the kernel of φ, viewed as a subset of the product monoid A^∗×A^∗ is a rational set.

A quasi-rational monoid is one for which L is a rational relation: a rational monoid is one for which there is also a rational function cross-section of L. Since L is a subset of a free monoid, Kleene's theorem holds and a rational function is just one that can be instantiated by a finite state transducer.

• A finite monoid is rational.
• A group is a rational monoid if and only if it is finite.
• A finitely generated free monoid is rational.
• The monoid M4 generated by the set {0,e, a,b, x,y} subject to relations in which e is the identity, 0 is an absorbing element, each of a and b commutes with each of x and y and ax = bx, ay = by = bby, xx = xy = yx = yy = 0 is rational but not automatic.
• The Fibonacci monoid, the quotient of the free monoid on two generators {a,b}^∗ by the congruence aab = bba.

The Green's relations for a rational monoid satisfy D = J.Sakarovitch (1987)

Kleene's theorem holds for rational monoids: that is, a subset is a recognisable set if and only if it is a rational set.

A rational monoid is not necessarily automatic, and vice versa. However, a rational monoid is asynchronously automatic and hyperbolic.

A rational monoid is a regulator monoid and a quasi-rational monoid: each of these implies that it is a Kleene monoid, that is, a monoid in which Kleene's theorem holds.

{{reflist}}

• {{cite book | last1=Fichtner | first1=Ina | last2=Mathissen | first2=Christian | chapter=Rational transformations and a Kleene theorem for power series over rational monoids | zbl=1350.68191 | editor1-last=Gomes | editor1-first=Gracinda M. S. | title=Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001 | location=Singapore | publisher= World Scientific | pages= 94–111 | year=2002 }}
• {{cite book | last1=Hoffmann | first1=Michael | last2=Kuske | first2=Dietrich | last3=Otto | first3=Friedrich | last4=Thomas | first4=Richard M. | chapter=Some relatives of automatic and hyperbolic groups | zbl=1031.20047 | editor1-last=Gomes | editor1-first=Gracinda M. S. | title=Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001 | location=Singapore | publisher= World Scientific | pages= 379–406 | year=2002 }}
• {{cite book | last=Kuich | first=Werner | chapter=Algebraic systems and pushdown automata | zbl=1251.68135 | editor1-last=Kuich | editor1-first=Werner | title=Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement | location=Berlin | publisher=Springer-Verlag | isbn=978-3-642-24896-2 | series=Lecture Notes in Computer Science | volume=7020 | pages=228–256 | year=2011 }}
• {{cite book | last=Pelletier | first= Maryse | chapter=Boolean closure and unambiguity of rational sets | zbl=0765.68075 | title=Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990 | editor1-last=Paterson | editor1-first=Michael S. | series=Lecture Notes in Computer Science | volume=443 | pages=512–525 | year=1990 }}
• {{cite journal | title=Easy multiplications I. The realm of Kleene's theorem | first=Jacques | last=Sakarovitch | journal=Information and Computation | volume=74| number=3 | date=September 1987 | pages=173–197 | doi=10.1016/0890-5401(87)90020-4 | zbl=0642.20043 | doi-access=free }}

Category:Algebraic structures

Category:Semigroup theory