In mathematics, an automatic semigroup is a finitely generated semigroup equipped with several regular languages over an alphabet representing a generating set. One of these languages determines "canonical forms" for the elements of the semigroup, the other languages determine if two canonical forms represent elements that differ by multiplication by a generator.
Formally, let be a semigroup and be a finite set of generators. Then an automatic structure for with respect to consists of a regular language over such that every element of has at least one representative in and such that for each , the relation consisting of pairs with is regular, viewed as a subset of (A# × A#)*. Here A# is A augmented with a padding symbol.[1]
The concept of an automatic semigroup was generalized from automatic groups by Campbell et al. (2001)
Unlike automatic groups (see Epstein et al. 1992), a semigroup may have an automatic structure with respect to one generating set, but not with respect to another. However, if an automatic semigroup has an identity, then it has an automatic structure with respect to any generating set (Duncan et al. 1999).
^Campbell, Colin M.; Robertson, Edmund F.; Ruskuc, Nik; Thomas, Richard M. (2001), "Automatic semigroups" (PDF), Theoretical Computer Science, 250 (1–2): 365–391, doi:10.1016/S0304-3975(99)00151-6.
and 24 Related for: Automatic semigroup information
In mathematics, an automaticsemigroup is a finitely generated semigroup equipped with several regular languages over an alphabet representing a generating...
mathematics, a semigroup is a nonempty set together with an associative binary operation. A special class of semigroups is a class of semigroups satisfying...
and semigroups. It follows that every monoid (or semigroup) arises as a homomorphic image of a free monoid (or semigroup). The study of semigroups as images...
groups to other structures. For instance, it generalizes naturally to automaticsemigroups. Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio...
In mathematics, a regular semigroup is a semigroup S in which every element is regular, i.e., for each element a in S there exists an element x in S such...
Markov semigroup describes the dynamics in a Markovian open quantum system. The axiomatic definition of the prototype of quantum Markov semigroups was first...
easy to see that this generates a semigroup in some sense—it is not absolutely integrable and so cannot define a semigroup in the above strong sense. Many...
paratopological groups are automatically topological groups. Artur Hideyuki Tomita. On sequentially compact both-sides cancellative semigroups with sequentially...
automata transformations or as semigroup homomorphisms, when the state space, S, of the automaton is defined as a semigroup Sg. Monoids are also considered...
Richard M. (2002). "Some relatives of automatic and hyperbolic groups". In Gomes, Gracinda M. S. (ed.). Semigroups, algorithms, automata and languages....
to the case of any commutative semigroup. Without the cancellation property the semigroup homomorphism from the semigroup into the group may be non-injective...
B (which is always possible if B is finite-dimensional), then it is automatically a bialgebra. (B, ∇, η, Δ, ε) is a bialgebra over K if it has the following...
on 2015-09-10. Lawson, J.; Madison, B. (1974). "Quotients of k-semigroups". Semigroup Forum. 9: 1–18. doi:10.1007/BF02194829., p. 3 Breuckmann, Tomas;...
multiplicative inverse Semigroup – an algebraic structure consisting of a set together with an associative binary operation Monoid – a semigroup with an identity...
more elements of A, with the binary operation of concatenation. The free semigroup A+ is the subsemigroup of A* containing all elements except the empty...
field F is large enough to contain a zero of this polynomial (which automatically happens for F algebraically closed, such as F = C) any linear map has...
constructed from a particular class of endomorphism of a free monoid. Every automatic sequence is morphic. Let f be an endomorphism of the free monoid A∗ on...
ring to the underlying rng. Adjoining an identity to a semigroup. Similarly, given a semigroup S, we can add an identity element and obtain a monoid by...
continuous exponents. This is the starting point of the mathematical theory of semigroups. Just as computing matrix powers with discrete exponents solves discrete...
ISBN 9780444520135. Schein, Boris M. (1970) "Relation algebras and function semigroups", Semigroup Forum 1: 1–62 Schmidt, Gunther (2010). Relational Mathematics. Cambridge...
Krohn–Rhodes complexity is an important topic in the study of finite semigroups and automata. In Network theory complexity is the product of richness...
Global Information
