Rational monoid explained
In mathematics, a rational monoid is a monoid, an algebraic structure, for which each element can be represented in a "normal form" that can be computed by a finite transducer: multiplication in such a monoid is "easy", in the sense that it can be described by a rational function.
Definition
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.
Examples
- 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 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 ∗ by the congruence aab = bba.
Green's relations
The Green's relations for a rational monoid satisfy D = J.[1]
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 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.
References
- Book: Fichtner . Ina . Mathissen . Christian . Rational transformations and a Kleene theorem for power series over rational monoids . 1350.68191 . Gomes . Gracinda M. S. . 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 . 94–111 . 2002 .
- Book: Hoffmann . Michael . Kuske . Dietrich . Otto . Friedrich . Thomas . Richard M. . Some relatives of automatic and hyperbolic groups . 1031.20047 . Gomes . Gracinda M. S. . 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 . 379–406 . 2002 .
- Book: Kuich, Werner . Algebraic systems and pushdown automata . 1251.68135 . Kuich . Werner . Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement . Berlin . . 978-3-642-24896-2 . Lecture Notes in Computer Science . 7020 . 228–256 . 2011 .
- Book: Pelletier, Maryse . Boolean closure and unambiguity of rational sets . 0765.68075 . Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990 . Paterson . Michael S. . Lecture Notes in Computer Science . 443 . 512–525 . 1990 .
- Easy multiplications I. The realm of Kleene's theorem . Jacques . Sakarovitch . Information and Computation . 74. 3 . September 1987 . 173–197 . 10.1016/0890-5401(87)90020-4 . 0642.20043 . free .
Notes and References
- Sakarovitch (1987)