Rational set
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 rational set generalizes the notion of rational (regular) language (understood as defined by regular expressions) to monoids that are not necessarily free. Definition. Let formula_1 be a monoid with identity element formula_2. The set formula_3 of rational subsets of formula_4 is the smallest set that contains  every finite set and is closed under This means that any rational subset of formula_4 can be obtained by taking a finite number of finite subsets of formula_4 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 formula_15 be an alphabet, the set formula_16 of words over formula_15 is a monoid. The rational subset of formula_16 are precisely the regular languages. Indeed, the regular languages may be defined by a finite regular expression. The rational subsets of formula_19 are the ultimately  periodic sets of integers. More generally, the rational subsets of formula_20 are the semilinear sets. Properties. McKnight's theorem states that if formula_4 is finitely generated then its recognizable subset are rational sets. This is not true in general, since the whole formula_4 is always recognizable but it is not rational if formula_4 is infinitely generated. Rational sets are closed under morphism: given formula_4 and formula_25 two monoids and formula_26 a morphism, if formula_27 then formula_28. formula_3 is not closed under complement as the following example shows. Let formula_30, the sets formula_31 and formula_32 are rational but formula_33 is not  because its projection to the second element formula_34 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. 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.