Rational monoid
In mathematics, a rational monoid is a monoid, an algebraic structure, for which each element can be represented in a "normal form" which 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 {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.
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
- ↑ Sakarovitch (1987)
- Fichtner, Ina; Mathissen, Christian (2002). "Rational transformations and a Kleene theorem for power series over rational monoids". In 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. pp. 94–111. Zbl 05970638.
- Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Some relatives of automatic and hyperbolic groups". In 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. pp. 379–406. Zbl 1031.20047.
- Kuich, Werner (2011). "Algebraic systems and pushdown automata". In Kuich, Werner. Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement. Lecture Notes in Computer Science 7020. Berlin: Springer-Verlag. pp. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135.
- Pelletier, Maryse (1990). "Boolean closure and unambiguity of rational sets". In Paterson, Michael S. Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990. Lecture Notes in Computer Science 443. pp. 512–525. Zbl 0765.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. Zbl 0642.20043.