HOME

TheInfoList



OR:

In mathematics and
theoretical computer science computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the ...
, a semiautomaton is a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
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. Associated with any semiautomaton is a
monoid 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. Monoids a ...
called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which
acts The Acts of the Apostles ( grc-koi, Πράξεις Ἀποστόλων, ''Práxeis Apostólōn''; la, Actūs Apostolōrum) is the fifth book of the New Testament; it tells of the founding of the Christian Church and the spread of its message ...
on the set of states ''Q''. This may be viewed either as an action of 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 elem ...
of strings in the input alphabet Σ, or as the induced
transformation semigroup In algebra, a transformation semigroup (or composition semigroup) is a collection of transformations ( functions from a set to itself) that is closed under function composition. If it includes the identity function, it is a monoid, called a transfo ...
of ''Q''. In older books like Clifford and Preston (1967) semigroup actions are called "operands". In
category theory Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cate ...
, semiautomata essentially are
functor In mathematics, specifically category theory, a functor is a mapping between categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) are associated to topological spaces, and ...
s.


Transformation semigroups and monoid acts

: A transformation semigroup or transformation monoid is a pair (M,Q) consisting of a set ''Q'' (often called the "set of states") and a
semigroup In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it. The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'' ...
or
monoid 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. Monoids a ...
''M'' of functions, or "transformations", mapping ''Q'' to itself. They are functions in the sense that every element ''m'' of ''M'' is a map m\colon Q\to Q. If ''s'' and ''t'' are two functions of the transformation semigroup, their semigroup product is defined as their
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
(st)(q)=(s\circ t)(q)=s(t(q)). Some authors regard "semigroup" and "monoid" as synonyms. Here a semigroup need not have an
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures ...
; a monoid is a semigroup with an identity element (also called "unit"). Since the notion of functions acting on a set always includes the notion of an identity function, which when applied to the set does nothing, a transformation semigroup can be made into a monoid by adding the identity function.


''M''-acts

Let ''M'' be a
monoid 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. Monoids a ...
and ''Q'' be a non-empty set. If there exists a multiplicative operation :\mu\colon Q\times M \to Q :(q,m)\mapsto qm=\mu(q,m) which satisfies the properties :q1=q for 1 the unit of the monoid, and :q(st)=(qs)t for all q\in Q and s,t\in M, then the triple (Q,M,\mu) is called a right ''M''-act or simply a right act. In long-hand, \mu is the ''right multiplication of elements of Q by elements of M''. The right act is often written as Q_M. A left act is defined similarly, with :\mu\colon M\times Q \to Q :(m,q)\mapsto mq=\mu(m,q) and is often denoted as \,_MQ. An ''M''-act is closely related to a transformation monoid. However the elements of ''M'' need not be functions ''per se'', they are just elements of some monoid. Therefore, one must demand that the action of \mu be consistent with multiplication in the monoid (''i.e.'' \mu(q, st)=\mu(\mu(q,s),t)), as, in general, this might not hold for some arbitrary \mu, in the way that it does for function composition. Once one makes this demand, it is completely safe to drop all parenthesis, as the monoid product and the action of the monoid on the set are completely
associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
. In particular, this allows elements of the monoid to be represented as strings of letters, in the computer-science sense of the word "string". This abstraction then allows one to talk about string operations in general, and eventually leads to the concept of
formal languages 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 sym ...
as being composed of strings of letters. Another difference between an ''M''-act and a transformation monoid is that for an ''M''-act ''Q'', two distinct elements of the monoid may determine the same transformation of ''Q''. If we demand that this does not happen, then an ''M''-act is essentially the same as a transformation monoid.


''M''-homomorphism

For two ''M''-acts Q_M and B_M sharing the same monoid M, an ''M''-homomorphism f\colon Q_M\to B_M is a map f\colon Q \to B such that :f(qm)=f(q)m for all q\in Q_M and m\in M. The set of all ''M''-homomorphisms is commonly written as \mathrm(Q_M, B_M) or \mathrm_M(Q, B). The ''M''-acts and ''M''-homomorphisms together form a
category Category, plural categories, may refer to: Philosophy and general uses *Categorization, categories in cognitive science, information science and generally *Category of being * ''Categories'' (Aristotle) *Category (Kant) *Categories (Peirce) *C ...
called ''M''-Act.


Semiautomata

A semiautomaton is a triple (Q,\Sigma,T) where \Sigma is a non-empty set, called the ''input alphabet'', ''Q'' is a non-empty set, called the ''set of states'', and ''T'' is the ''transition function'' :T\colon Q\times \Sigma \to Q. When the set of states ''Q'' is a finite set—it need not be—, a semiautomaton may be thought of as a
deterministic finite automaton In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automa ...
(Q,\Sigma,T,q_0,A), but without the initial state q_0 or set of
accept state A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
s ''A''. Alternately, it is a
finite state machine A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
that has no output, and only an input. Any semiautomaton induces an act of a monoid in the following way. Let \Sigma^* be 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 elem ...
generated by the
alphabet An alphabet is a standardized set of basic written graphemes (called letter (alphabet), letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character ...
\Sigma (so that the superscript * is understood to be the
Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) 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 ...
); it is the set of all finite-length strings composed of the letters in \Sigma. For every word ''w'' in \Sigma^*, let T_w\colon Q\to Q be the function, defined recursively, as follows, for all ''q'' in ''Q'': * If w=\varepsilon, then T_\varepsilon(q)=q, so that the
empty word In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...
\varepsilon does not change the state. * If w=\sigma is a letter in \Sigma, then T_\sigma(q)=T(q,\sigma). * If w=\sigma v for \sigma\in\Sigma and v\in \Sigma^*, then T_w(q)=T_v(T_\sigma(q)). Let M(Q,\Sigma,T) be the set :M(Q,\Sigma,T)=\. The set M(Q,\Sigma,T) is closed under
function composition In mathematics, function composition is an operation that takes two functions and , and produces a function such that . In this operation, the function is applied to the result of applying the function to . That is, the functions and ...
; that is, for all v,w\in\Sigma^*, one has T_w\circ T_v=T_. It also contains T_\varepsilon, which is the
identity function Graph of the identity function on the real numbers In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, un ...
on ''Q''. Since function composition is
associative In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement ...
, the set M(Q,\Sigma,T) is a monoid: it is called the input monoid, characteristic monoid, characteristic semigroup or transition monoid of the semiautomaton


Properties

If the set of states ''Q'' is finite, then the transition functions are commonly represented as
state transition table State may refer to: Arts, entertainment, and media Literature * ''State Magazine'', a monthly magazine published by the U.S. Department of State * ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States * '' Our ...
s. The structure of all possible transitions driven by strings in the free monoid has a graphical depiction as a
de Bruijn graph In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple ...
. The set of states ''Q'' need not be finite, or even countable. As an example, semiautomata underpin the concept of
quantum finite automata In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of a ...
. There, the set of states ''Q'' are given by the
complex projective space In mathematics, complex projective space is the projective space with respect to the field of complex numbers. By analogy, whereas the points of a real projective space label the lines through the origin of a real Euclidean space, the points of ...
\mathbbP^n, and individual states are referred to as ''n''-state
qubit In quantum computing, a qubit () or quantum bit is a basic unit of quantum information—the quantum version of the classic binary bit physically realized with a two-state device. A qubit is a two-state (or two-level) quantum-mechanical system, ...
s. State transitions are given by unitary ''n''×''n'' matrices. The input alphabet \Sigma remains finite, and other typical concerns of automata theory remain in play. Thus, the quantum semiautomaton may be simply defined as the triple (\mathbbP^n,\Sigma,\) when the alphabet \Sigma has ''p'' letters, so that there is one unitary matrix U_\sigma for each letter \sigma\in\Sigma. Stated in this way, the quantum semiautomaton has many geometrical generalizations. Thus, for example, one may take a
Riemannian symmetric space In mathematics, a symmetric space is a Riemannian manifold (or more generally, a pseudo-Riemannian manifold) whose group of symmetries contains an inversion symmetry about every point. This can be studied with the tools of Riemannian geometry, ...
in place of \mathbbP^n, and selections from its group of
isometries In mathematics, an isometry (or congruence, or congruent transformation) is a distance-preserving transformation between metric spaces, usually assumed to be bijective. The word isometry is derived from the Ancient Greek: ἴσος ''isos'' me ...
as transition functions. The
syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. Syntactic quotient The free monoid on a given set is the monoid whose elements are all the strings of z ...
of a
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
is
isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...
to the transition monoid of the
minimal automaton In automata theory (a branch of theoretical computer science), DFA minimization is the task of transforming a given deterministic finite automaton (DFA) into an equivalent DFA that has a minimum number of states. Here, two DFAs are called equival ...
accepting the language.


References

* A. H. Clifford and G. B. Preston, ''The Algebraic Theory of Semigroups''. American Mathematical Society, volume 2 (1967), . * F. Gecseg and I. Peak, ''Algebraic Theory of Automata'' (1972), Akademiai Kiado, Budapest. * W. M. L. Holcombe, ''Algebraic Automata Theory'' (1982), Cambridge University Press * J. M. Howie, ''Automata and Languages'', (1991), Clarendon Press, . * Mati Kilp, Ulrich Knauer, Alexander V. Mikhalov, ''Monoids, Acts and Categories'' (2000), Walter de Gruyter, Berlin, . * Rudolf Lidl and Günter Pilz, ''Applied Abstract Algebra'' (1998), Springer, {{isbn, 978-0-387-98290-8 Category theory Semigroup theory Finite automata