Rational monoid

In mathematics, arational monoidis amonoid,an algebraic structure, for which each element can be represented in a "normal form" that can be computed by afinite transducer:multiplication in such a monoid is "easy", in the sense that it can be described by arational function.

Definition

Consider a monoidM.Consider a pair (A,L) whereAis a finite subset ofMthat generatesMas a monoid, andLis a language onA(that is, a subset of the set of all stringsA^∗). Letφbe the map from thefree monoidA^∗toMgiven by evaluating a string as a product inM.We say thatLis arational cross-sectionifφinduces a bijection betweenLandM.We say that (A,L) is arational structureforMif in addition thekernelofφ,viewed as a subset of the product monoidA^∗×A^∗is arational set.

Aquasi-rational monoidis one for whichLis arational relation:arational monoidis one for which there is also arational functioncross-section ofL.SinceLis a subset of a free monoid,Kleene's theoremholds and a rational function is just one that can be instantiated by a finite state transducer.

Examples

• A finite monoid is rational.
• Agroupis 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 whicheis the identity, 0 is anabsorbing element,each ofaandbcommutes with each ofxandyandax=bx,ay=by=bby,xx=xy=yx=yy= 0 is rational but not automatic.
• TheFibonacci monoid,the quotient of the free monoid on two generators {a,b}^∗by the congruenceaab=bba.

Green's relations

TheGreen's relationsfor a rational monoid satisfyD=J.

Properties

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 necessarilyautomatic,and vice versa. However, a rational monoid is asynchronously automatic andhyperbolic.

A rational monoid is aregulator monoidand aquasi-rational monoid:each of these implies that it is aKleene monoid,that is, a monoid in which Kleene's theorem holds.

References

• Fichtner, Ina; Mathissen, Christian (2002). "Rational transformations and a Kleene theorem for power series over rational monoids". In Gomes, Gracinda M. S. (ed.).Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001.Singapore: World Scientific. pp. 94–111.Zbl1350.68191.
• Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Some relatives of automatic and hyperbolic groups". In Gomes, Gracinda M. S. (ed.).Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001.Singapore: World Scientific. pp. 379–406.Zbl1031.20047.
• Kuich, Werner (2011). "Algebraic systems and pushdown automata". In Kuich, Werner (ed.).Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement.Lecture Notes in Computer Science. Vol. 7020. Berlin:Springer-Verlag.pp. 228–256.ISBN978-3-642-24896-2.Zbl1251.68135.
• Pelletier, Maryse (1990). "Boolean closure and unambiguity of rational sets". In Paterson, Michael S. (ed.).Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990.Lecture Notes in Computer Science. Vol. 443. pp. 512–525.Zbl0765.68075.
• Sakarovitch, Jacques (September 1987)."Easy multiplications I. The realm of Kleene's theorem".Information and Computation.74(3): 173–197.doi:10.1016/0890-5401(87)90020-4.Zbl0642.20043.