mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

and

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

, a rational series is a generalisation of the concept of

formal power series In mathematics, a formal series is an infinite sum that is considered independently from any notion of convergence, and can be manipulated with the usual algebraic operations on series (addition, subtraction, multiplication, division, partial sum ...

over a

ring Ring may refer to: * Ring (jewellery), a round band, usually made of metal, worn as ornamental jewelry * To make a sound with a bell, and the sound made by a bell :(hence) to initiate a telephone connection Arts, entertainment and media Film and ...

to the case when the basic algebraic structure is no longer a ring but a

semiring 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. The term rig is also used occasionally—this originated as a joke, suggesting that rigs ar ...

, and the indeterminates adjoined are not assumed to

commute Commute, commutation or commutative may refer to: * Commuting, the process of travelling between a place of residence and a place of work Mathematics * Commutative property, a property of a mathematical operation whose result is insensitive to th ...

. They can be regarded as algebraic expressions of a

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

over a finite

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

Definition

Let ''R'' be a

and ''A'' a finite alphabet. A ''non-commutative polynomial'' over ''A'' is a finite formal sum of words over ''A''. They form a semiring

R\langle A \rangle

. A ''formal series'' is a ''R''-valued function ''c'', on the

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...

''A''^*, which may be written as :

\sum_ c(w) w .

The set of formal series is denoted

R\langle\langle A \rangle\rangle

and becomes a semiring under the operations :

c+d : w \mapsto c(w) + d(w)

c\cdot d : w \mapsto \sum_ c(u) \cdot d(v)

A non-commutative polynomial thus corresponds to a function ''c'' on ''A''^* of finite

support Support may refer to: Arts, entertainment, and media * Supporting character Business and finance * Support (technical analysis) * Child support * Customer support * Income Support Construction * Support (structure), or lateral support, a ...

. In the case when ''R'' is a ring, then this is the ''Magnus ring'' over ''R''. If ''L'' is a language over ''A'', regarded as a subset of ''A''^* we can form the ''characteristic series'' of ''L'' as the formal series :

\sum_ w

corresponding to the

characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts: * The indicator function of a subset, that is the function ::\mathbf_A\colon X \to \, :which for a given subset ''A'' of ''X'', has value 1 at points ...

of ''L''. In

R\langle\langle A \rangle\rangle

one can define an operation of

iteration Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...

expressed as :

S^* = \sum_ S^n

and formalised as :

c^*(w) = \sum_ c(u_1)c(u_2) \cdots c(u_n) .

The ''rational operations'' are the addition and multiplication of formal series, together with iteration. A rational series is a formal series obtained by rational operations from

R\langle A \rangle.

Definition

See also

References

Further reading