Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Semiautomaton
Summary
In mathematics and theoretical computer science, a semiautomaton is a deterministic finite automaton 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 called the characteristic monoid, input monoid, transition monoid or transition system of the semiautomaton, which acts on the set of states Q. This may be viewed either as an action of the free monoid of strings in the input alphabet Σ, or as the induced transformation semigroup of Q.
In older books like Clifford and Preston (1967) semigroup actions are called "operands".
In , semiautomata essentially are functors.
semigroup action
A transformation semigroup or transformation monoid is a pair consisting of a set Q (often called the "set of states") and a semigroup or monoid 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 .
Some authors regard "semigroup" and "monoid" as synonyms. Here a semigroup need not have an identity element; 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.
Let M be a monoid 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.