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

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

  1. Sakarovitch (1987)
This article is issued from Wikipedia - version of the 7/5/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.