In
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
theoretical computer science
Theoretical 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 circumsc ...
, 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 autom ...
having inputs but no output. It consists of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''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 ...
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 eleme ...
of
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
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 transf ...
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 Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
s.
Transformation semigroups and monoid acts
:
A transformation semigroup or transformation monoid is a pair
consisting of a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''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 ...
''M'' of
functions, or "transformations", mapping ''Q'' to itself. They are functions in the sense that every element ''m'' of ''M'' is a map
. 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 ...
.
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 su ...
; 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 ...
and ''Q'' be a non-empty set. If there exists a multiplicative operation
:
:
which satisfies the properties
:
for 1 the unit of the monoid, and
:
for all
and
, then the triple
is called a right ''M''-act or simply a right act. In long-hand,
is the ''right multiplication of elements of Q by elements of M''. The right act is often written as
.
A left act is defined similarly, with
:
:
and is often denoted as
.
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
be consistent with multiplication in the monoid (''i.e.''
), as, in general, this might not hold for some arbitrary
, 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 f ...
. In particular, this allows elements of the monoid to be represented as
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
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 string (computer science), words whose symbol (formal), letters are taken from an alphabet (formal languages), alphabet and are well-formedness, well-formed ...
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
and
sharing the same monoid
, an ''M''-homomorphism
is a map
such that
:
for all
and
. The set of all ''M''-homomorphisms is commonly written as
or
.
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)
* ...
called ''M''-Act.
Semiautomata
A semiautomaton is a triple
where
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''
:
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 autom ...
, but without the initial state
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
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 eleme ...
generated by the
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 ...
(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 c ...
); it is the set of all finite-length
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
composed of the letters in
.
For every word ''w'' in
, let
be the function, defined recursively, as follows, for all ''q'' in ''Q'':
* If
, then
, 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 ...
does not change the state.
* If
is a letter in
, then
.
* If
for
and
, then
.
Let
be the set
:
The set
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
, one has
. It also contains
, 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 f ...
, the set
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 ...
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 ...
. 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 a ...
, 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
remains finite, and other typical concerns of automata theory remain in play. Thus, the quantum semiautomaton may be simply defined as the triple
when the alphabet
has ''p'' letters, so that there is one unitary matrix
for each letter
. 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
, 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'' mea ...
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 zero ...
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
Alfred Hoblitzelle Clifford (July 11, 1908 – December 27, 1992) was an American mathematician born in St. Louis, Missouri who is known for Clifford theory and for his work on semigroups. He did his undergraduate studies at Yale University, Yal ...
and
G. B. Preston
Gordon Bamford Preston (28 April 1925 – 14 April 2015) was an English mathematician best known for his work on semigroups. He received his D.Phil. in mathematics in 1954 from Magdalen College, Oxford.
He was born in Workington and broug ...
, ''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