Editing Semigroup action (section)

==Applications to computer science==
===Semiautomata===

{{main|Semiautomaton}}

Transformation semigroups are of essential importance for the structure theory of [[finite-state machine]]s in [[automata theory]]. In particular, a ''semiautomaton'' is a triple (Σ,''X'',''T''), where Σ is a non-empty set called the ''input alphabet'', ''X'' is a non-empty set called the ''set of states'' and ''T'' is a function
:<math>T\colon \Sigma\times X \to X</math>
called the ''transition function''. Semiautomata arise from [[deterministic finite automaton|deterministic automata]] by ignoring the initial state and the set of accept states.

Given a semiautomaton, let ''T''<sub>''a''</sub>: ''X'' → ''X'', for ''a'' ∈ Σ, denote the transformation of ''X'' defined by ''T''<sub>''a''</sub>(''x'') = ''T''(''a'',''x''). Then the semigroup of transformations of ''X'' generated by {''T''<sub>''a''</sub> : ''a'' ∈ Σ} is called the ''[[characteristic semigroup]]'' or ''transition system'' of (Σ,''X'',''T''). This semigroup is a monoid, so this monoid is called the ''characteristic'' or ''[[transition monoid]]''. It is also sometimes viewed as a Σ<sup>∗</sup>-act on ''X'', where Σ<sup>∗</sup> is the [[free monoid]] of strings generated by the alphabet Σ,<ref group="note">The monoid operation is concatenation; the identity element is the empty string.</ref> and the action of strings extends the action of Σ via the property
:<math>T_{vw} = T_w \circ T_v.</math>

===Krohn–Rhodes theory===

{{main|Krohn–Rhodes theory}}

Krohn–Rhodes theory, sometimes also called ''algebraic automata theory'', gives powerful decomposition results for finite transformation semigroups by cascading simpler components.