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.
Let R be a semiring and A a finite alphabet.
A non-commutative polynomial over A is a finite formal sum of words over A. They form a semiring .
A formal series is a R-valued function c, on the free monoid A*, which may be written as
The set of formal series is denoted and becomes a semiring under the operations
A non-commutative polynomial thus corresponds to a function c on A* of finite support.
In the case when R is a ring, then this is the Magnus ring over R. [1]
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
corresponding to the characteristic function of L.
In one can define an operation of iteration expressed as
and formalised as
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
In mathematics, an inner product space is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, often denoted with angle brackets such as in . Inner products allow formal definitions of intuitive geometric notions, such as lengths, angles, and orthogonality of vectors. Inner product spaces generalize Euclidean vector spaces, in which the inner product is the dot product or scalar product of Cartesian coordinates. Inner product spaces of infinite dimension are widely used in functional analysis. Inner product spaces over the field of complex numbers are sometimes referred to as unitary spaces. The first usage of the concept of a vector space with an inner product is due to Giuseppe Peano, in 1898.
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".
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, 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.
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 abstract algebra, a matrix ring is a set of matrices with entries in a ring R that form a ring under matrix addition and matrix multiplication (Lam 1999). The set of all n × n matrices with entries in R is a matrix ring denoted Mn(R) (alternative notations: Matn(R) and Rn×n). Some sets of infinite matrices form infinite matrix rings. Any subring of a matrix ring is a matrix ring. Over a rng, one can form matrix rngs.
In the mathematical fields of linear algebra and functional analysis, the orthogonal complement of a subspace W of a vector space V equipped with a bilinear form B is the set W⊥ of all vectors in V that are orthogonal to every vector in W. Informally, it is called the perp, short for perpendicular complement. It is a subspace of V.
A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines relations between sets of strings.
In mathematics, the Lasker–Noether theorem states that every Noetherian ring is a Lasker ring, which means that every ideal can be decomposed as an intersection, called primary decomposition, of finitely many primary ideals. The theorem was first proven by Emanuel Lasker (1905) for the special case of polynomial rings and convergent power series rings, and was proven in its full generality by Emmy Noether (1921).
In mathematics, a Witt group of a field, named after Ernst Witt, is an abelian group whose elements are represented by symmetric bilinear forms over the field.
In commutative algebra, the Hilbert function, the Hilbert polynomial, and the Hilbert series of a graded commutative algebra finitely generated over a field are three strongly related notions which measure the growth of the dimension of the homogeneous components of the algebra.
In mathematics, specifically ring theory, the notion of quasiregularity provides a computationally convenient way to work with the Jacobson radical of a ring. In this article, we primarily concern ourselves with the notion of quasiregularity for unital rings. However, one section is devoted to the theory of quasiregularity in non-unital rings, which constitutes an important aspect of noncommutative ring theory.
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 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.
In theoretical computer science and formal language theory, a weighted automaton or weighted finite-state machine is a generalization of a finite-state machine in which the edges have weights, for example real numbers or integers. Finite-state machines are only capable of answering decision problems; they take as input a string and produce a Boolean output, i.e. either "accept" or "reject". In contrast, weighted automata produce a quantitative output, for example a count of how many answers are possible on a given input string, or a probability of how likely the input string is according to a probability distribution. They are one of the simplest studied models of quantitative automata.
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 algebra, the ring of restricted power series is the subring of a formal power series ring that consists of power series whose coefficients approach zero as degree goes to infinity. Over a non-archimedean complete field, the ring is also called a Tate algebra. Quotient rings of the ring are used in the study of a formal algebraic space as well as rigid analysis, the latter over non-archimedean complete fields.
In mathematics, a formal distribution is an infinite sum of powers of a formal variable, usually denoted in the theory of formal distributions. The coefficients of these infinite sums can be many different mathematical structures, such as vector spaces or rings, but in applications most often take values in an algebra over a field. These infinite sums are allowed to have infinitely many positive and negative powers, and are not required to converge, and so do not define functions of the formal variable. Rather, they are interpreted as distributions, that is, linear functionals on an appropriate space of test functions. They are closely related to formal Laurent series, but are not required to have finitely many negative powers. In particular, this means even if the coefficients are ring-valued, it is not necessarily possible to multiply two formal distributions.