In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, more precisely in
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
, a rational set of a
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
is an element of the minimal class of subsets of this monoid that contains all finite subsets and is closed under
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
, product and
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) 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 c ...
. Rational sets are useful in
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
,
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
s and
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
.
A rational set generalizes the notion of
rational (regular) language (understood as defined by
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
s) to monoids that are not necessarily
free.
Definition
Let
be a
monoid
In abstract algebra, a branch of mathematics, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being 0.
Monoids ...
with identity element
. The set
of rational subsets of
is the smallest set that contains every finite set and is closed under
*
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''Un ...
: if
then
* product: if
then
*
Kleene star
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) 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 c ...
: if
then
where
is the singleton containing the identity element, and where
.
This means that any rational subset of
can be obtained by taking a finite number of finite subsets of
and applying the union, product and Kleene star operations a finite number of times.
In general a rational subset of a monoid is not a submonoid.
Example
Let
be an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
, the set
of words over
is a monoid. The rational subset of
are precisely the
regular language
In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
s. Indeed, the regular languages may be defined by a finite
regular expression
A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
.
The rational subsets of
are the ultimately periodic sets of integers. More generally, the rational subsets of
are the
semilinear sets.
Properties
McKnight's theorem states that if
is finitely generated then its
recognizable subset are rational sets.
This is not true in general, since the whole
is always recognizable but it is not rational if
is infinitely generated.
Rational sets are closed under morphism: given
and
two monoids and
a morphism, if
then
.
is not closed under
complement
A complement is something that completes something else.
Complement may refer specifically to:
The arts
* Complement (music), an interval that, when added to another, spans an octave
** Aggregate complementation, the separation of pitch-class ...
as the following example shows.
Let
, the sets
and
are rational but
is not because its projection to the second element
is not rational.
The intersection of a rational subset and of a recognizable subset is rational.
For finite groups the following result of A. Anissimov and A. W. Seifert is well known: a
subgroup
In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
''H'' of a
finitely generated group
In algebra, a finitely generated group is a group ''G'' that has some finite generating set ''S'' so that every element of ''G'' can be written as the combination (under the group operation) of finitely many elements of ''S'' and of inverses of s ...
''G'' is recognizable if and only if ''H'' has
finite index In mathematics, specifically group theory, the index of a subgroup ''H'' in a group ''G'' is the
number of left cosets of ''H'' in ''G'', or equivalently, the number of right cosets of ''H'' in ''G''.
The index is denoted , G:H, or :H/math> or (G ...
in ''G''. In contrast, ''H'' is rational if and only if ''H'' is finitely generated.
[preprint]
/ref>
Rational relations and rational functions
A binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
between monoids ''M'' and ''N'' is a rational relation if the graph of the relation, regarded as a subset of ''M''×''N'' is a rational set in the product monoid. A function from ''M'' to ''N'' is a rational function if the graph of the function is a rational set.
See also
* Rational series 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 ...
* Recognizable set
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.
This ...
* Rational monoid
References
*
*Jean-Éric Pin
Jean-Éric Pin is a French mathematician and theoretical computer scientist known for his contributions to the algebraic automata theory and semigroup theory. He is a CNRS research director.
Biography
Pin earned his undergraduate degree from ENS ...
Mathematical Foundations of Automata Theory
Chapter IV: Recognisable and rational sets
*Samuel Eilenberg
Samuel Eilenberg (September 30, 1913 – January 30, 1998) was a Polish-American mathematician who co-founded category theory (with Saunders Mac Lane) and homological algebra.
Early life and education
He was born in Warsaw, Kingdom of Poland to a ...
and M. P. Schützenberger
Rational Sets in Commutative Monoids
Journal of Algebra, 1969.
Further reading
* {{cite book , last=Sakarovitch , first=Jacques , title=Elements of automata theory , others=Translated from the French by Reuben Thomas , location=Cambridge , publisher=Cambridge University Press , year=2009 , isbn=978-0-521-84425-3 , zbl=1188.68177 , at = Part II: The power of algebra
Automata (computation)