Rational set

Last updated March 02, 2024

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.

Definition

Let $(N,\cdot )$ be a monoid with identity element $e$ . The set $\mathrm {RAT} (N)$ of rational subsets of $N$ is the smallest set that contains every finite set and is closed under

union: if $A,B\in \mathrm {RAT} (N)$ then $A\cup B\in \mathrm {RAT} (N)$
product: if $A,B\in \mathrm {RAT} (N)$ then $A\cdot B=\{a\cdot b\mid a\in A,b\in B\}\in \mathrm {RAT} (N)$
Kleene star: if $A\in \mathrm {RAT} (N)$ then $A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {RAT} (N)$ where $A^{0}=\{e\}$ is the singleton containing the identity element, and where $A^{n+1}=A^{n}\cdot A$ .

This means that any rational subset of $N$ can be obtained by taking a finite number of finite subsets of $N$ 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 $A$ be an alphabet, the set $A^{*}$ of words over $A$ is a monoid. The rational subset of $A^{*}$ are precisely the regular languages. Indeed, the regular languages may be defined by a finite regular expression.

The rational subsets of $\mathbb {N}$ are the ultimately periodic sets of integers. More generally, the rational subsets of $\mathbb {N} ^{k}$ are the semilinear sets.^[1]

Properties

McKnight's theorem states that if $N$ is finitely generated then its recognizable subset are rational sets. This is not true in general, since the whole $N$ is always recognizable but it is not rational if $N$ is infinitely generated.

Rational sets are closed under homomorphism: given $N$ and $M$ two monoids and $\phi :N\rightarrow M$ a monoid homomorphism, if $S\in \mathrm {RAT} (N)$ then $\phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {RAT} (M)$ .

$\mathrm {RAT} (N)$ is not closed under complement as the following example shows.^[2] Let $N=\{a\}^{*}\times \{b,c\}^{*}$ , the sets $R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}$ and $S=(1,b)^{*}(a,c)^{*}=\{(a^{n},b^{m}c^{n})\mid n,m\in \mathbb {N} \}$ are rational but $R\cap S=\{(a^{n},b^{n}c^{n})\mid n\in \mathbb {N} \}$ is not because its projection to the second element $\{b^{n}c^{n}\mid n\in \mathbb {N} \}$ 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 H of a finitely generated group G is recognizable if and only if H has finite index in G. In contrast, H is rational if and only if H is finitely generated.^[3]

Rational relations and rational functions

A binary relation 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.^[4]

Related Research Articles

In mathematics, any vector space has a corresponding dual vector space consisting of all linear forms on together with the vector space structure of pointwise addition and scalar multiplication by constants.

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 $is written as . 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 repetitions".$

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

In mathematics, a group is a set with an operation that satisfies the following constraints: the operation is associative and has an identity element, and every element of the set has an inverse element.

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$ .

In theoretical computer science and formal language theory, a regular language is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science.

In mathematics, in particular abstract algebra, a graded ring is a ring such that the underlying additive group is a direct sum of abelian groups $such that . The index set is usually the set of nonnegative integers or the set of integers, but can be any monoid. The direct sum decomposition is usually referred to as gradation or grading .$

In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring formed from the set of polynomials in one or more indeterminates with coefficients in another ring, often a field.

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 mathematics and computer science, the syntactic monoid $of a formal language is the smallest monoid that recognizes the language .$

In algebra and theoretical computer science, an action or act of a semigroup on a set is a rule which associates to each element of the semigroup a transformation of the set in such a way that the product of two elements of the semigroup is associated with the composite of the two corresponding transformations. The terminology conveys the idea that the elements of the semigroup are acting as transformations of the set. From an algebraic perspective, a semigroup action is a generalization of the notion of a group action in group theory. From the computer science point of view, semigroup actions are closely related to automata: the set models the state of the automaton and the action models transformations of that state in response to inputs.

In mathematics, the Grothendieck group, or group of differences, of a commutative monoid $M$ is a certain abelian group. This abelian group is constructed from $M$ in the most universal way, in the sense that any abelian group containing a homomorphic image of $M$ will also contain a homomorphic image of the Grothendieck group of $M$ . The Grothendieck group construction takes its name from a specific case in category theory, introduced by Alexander Grothendieck in his proof of the Grothendieck–Riemann–Roch theorem, which resulted in the development of K-theory. This specific case is the monoid of isomorphism classes of objects of an abelian category, with the direct sum as its operation.

In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton having inputs but no output. It consists of a set Q of states, a set Σ called the input alphabet, and a function T: Q × Σ → Q called the transition function.

In mathematics, specifically in combinatorial commutative algebra, a convex lattice polytope P is called normal if it has the following property: given any positive integer n, every lattice point of the dilation nP, obtained from P by scaling its vertices by the factor n and taking the convex hull of the resulting points, can be written as the sum of exactly n lattice points in P. This property plays an important role in the theory of toric varieties, where it corresponds to projective normality of the toric variety determined by P. Normal polytopes have popularity in algebraic combinatorics. These polytopes also represent the homogeneous case of the Hilbert bases of finite positive rational cones and the connection to algebraic geometry is that they define projectively normal embeddings of toric varieties.

In algebra, a transformation semigroup is a collection of transformations 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.

Gordan's lemma is a lemma in convex geometry and algebraic geometry. It can be stated in several ways.

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism 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, 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 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 ways, 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

Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Chapter 7: Automata". Discrete Algebraic Methods. Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets
Samuel Eilenberg and Marcel-Paul Schützenberger, Rational Sets in Commutative Monoids, Journal of Algebra, 1969.

↑ Mathematical Foundations of Automata Theory
↑ cf. Jean-Éric Pin, Mathematical Foundations of Automata Theory, p. 76, Example 1.3
↑ John Meakin (2007). "Groups and semigroups: connections and contrasts". In C.M. Campbell; M.R. Quick; E.F. Robertson; G.C. Smith (eds.). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 376. ISBN 978-0-521-69470-4. preprint
↑ Hoffmann, Michael; Kuske, Dietrich; Otto, Friedrich; Thomas, Richard M. (2002). "Some relatives of automatic and hyperbolic groups". In Gomes, Gracinda M. S. (ed.). 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.