Rational monoid

Last updated

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.

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

Contents

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.

In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.

In computer science, more precisely in automata theory, a rational set of a monoid is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under union, product and Kleene star. Rational sets are useful in automata theory, formal languages and algebra.

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

Group (mathematics) Algebraic structure with one binary operation

In mathematics, a group is a set equipped with a binary operation that combines any two elements to form a third element in such a way that four conditions called group axioms are satisfied, namely closure, associativity, identity and invertibility. One of the most familiar examples of a group is the set of integers together with the addition operation, but groups are encountered in numerous areas within and outside mathematics, and help focusing on essential structural aspects, by detaching them from the concrete nature of the subject of the study.

In mathematics, an absorbing element is a special type of element of a set with respect to a binary operation on that set. The result of combining an absorbing element with any element of the set is the absorbing element itself. In semigroup theory, the absorbing element is called a zero element because there is no risk of confusion with other notions of zero. In this article the two notions are synonymous.

Green's relations

The Green's relations for a rational monoid satisfy D = J. [1]

In mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for James Alexander Green, who introduced them in a paper of 1951. John Mackintosh Howie, a prominent semigroup theorist, described this work as "so all-pervading that, on encountering a new semigroup, almost the first question one asks is 'What are the Green relations like?'". The relations are useful for understanding the nature of divisibility in a semigroup; they are also valid for groups, but in this case tell us nothing useful, because groups always have divisibility.

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.

In mathematics, an automatic semigroup is a finitely generated semigroup equipped with several regular languages over an alphabet representing a generating set. One of these languages determines "canonical forms" for the elements of the semigroup, the other languages determine if two canonical forms represent elements that differ by multiplication by a generator.

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.

Related Research Articles

In mathematical logic and computer science, the Kleene star is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics it is more commonly known as the free monoid construction. The application of the Kleene star to a set V is written as V*. It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterize certain automata, where it means "zero or more".

  1. If V is a set of strings, then V* is defined as the smallest superset of V that contains the empty string ε and is closed under the string concatenation operation.
  2. If V is a set of symbols or characters, then V* is the set of all strings over symbols in V, including the empty string ε.

In theoretical computer science and formal language theory, a regular language is a formal language that can be expressed using a regular expression, in the strict sense of the latter notion used in theoretical computer science.

In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative binary operation.

Generating set of a group Subset of a group such that all group elements can be expressed by finitely many group operations on its elements

In abstract algebra, a generating set of a group is a subset such that every element of the group can be expressed as a combination of finitely many elements of the subset and their inverses.

In mathematics, a Kleene algebra is an idempotent semiring endowed with a closure operator. It generalizes the operations known from regular expressions.

In abstract algebra, a semiring is an algebraic structure similar to a ring, but without the requirement that each element must have an additive inverse.

In mathematics and computer science, the Krohn–Rhodes theory is an approach to the study of finite semigroups and automata that seeks to decompose them in terms of elementary components. These components correspond to finite aperiodic semigroups and finite simple groups that are combined together in a feedback-free manner.

The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expressions are defined like regular expressions, but they have a built-in complement operator. For a regular language, its generalized star height is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem.

In mathematics, an aperiodic semigroup is a semigroup S such that every element x ∈ S is aperiodic, that is, for each x there exists a positive integer n such that xn = xn + 1. An aperiodic monoid is an aperiodic semigroup which is a monoid.

In mathematics and computer science, the syntactic monoidM(L) of a formal language L is the smallest monoid that recognizes the language L.

In algebra, a transformation semigroup is a collection of functions from a set to itself that is closed under function composition. If it includes the identity function, it is a monoid, called a transformationmonoid. This is the semigroup analogue of a permutation group.

In mathematics, particularly in abstract algebra, a semigroup with involution or a *-semigroup is a semigroup equipped with an involutive anti-automorphism, which—roughly speaking—brings it closer to a group because this involution, considered as unary operator, exhibits certain fundamental properties of the operation of taking the inverse in a group: uniqueness, double application "cancelling itself out", and the same interaction law with the binary operation as in the case of the group inverse. It is thus not a surprise that any group is a semigroup with involution. However, there are significant natural examples of semigroups with involution that are not groups.

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

In mathematics and computer science, a rational series is a generalisation of the concept of formal power series over a ring to the case when the basic algebraic structure is no longer a ring but a semiring, and the indeterminates adjoined are not assumed to commute. They can be regarded as algebraic expressions of a formal language over a finite alphabet.

In mathematics, and more precisely in semigroup theory, a variety of finite semigroups is a class of semigroups having some nice algebraic properties. Those classes can be defined in two distinct way, using either algebraic notions or topological notions. Varieties of finite monoids, varieties of finite ordered semigroups and varieties of finite ordered monoids are defined similarly.

References

  1. ↑ Sakarovitch (1987)

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.