characteristic monoid

Given a semiautomaton M=(S,Σ,δ), the transition function is typically defined as a function from S×Σ to S. One may instead think of δ as a set C(M) of functions

C(M):={δa:SSaΣ},where  δa(s):=δ(s,a).

Since the transition function δ in M can be extended to the domain S×Σ*, so can the set C(M):

C(M):={δu:SSuΣ*},where  δu(s):=δ(s,u).

The advantage of this interpreation is the following: for any input words u,v over Σ:


which can be easily verified:


In particular, δλ is the identity function on S, so that the set C(M) becomes a monoid, called the characteristic monoid of M.

The characteristic monoid C(M) of a semiautomaton M is related to the free monoid Σ* generated by Σ in the following manner: define a binary relationMathworldPlanetmath on Σ* by uv iff δu=δv. Then is clearly an equivalence relationMathworldPlanetmath on Σ*. It is also a congruence relationPlanetmathPlanetmath with respect to concatenationMathworldPlanetmath: if uv, then for any w over Σ:




Putting the two together, we see that if xy, then uxvxvy. We denote [u] the congruence class in Σ*/ containing the word u.

Now, define a map ϕ:C(M)Σ*/ by setting ϕ(δu)=[u]. Then ϕ is well-defined. Furthermore, under ϕ, it is easy to see that C(M) is anti-isomorphic to Σ*/.

Remark. In order to avoid using anti-isomorphisms, the usual practice is to introduce a multiplicationPlanetmathPlanetmath on C(M) so that δuδv:=δvδu. Then C(M) under is isomorphicPlanetmathPlanetmathPlanetmath to Σ*/.

Some properties:

  • If M and N are isomorphic semiautomata with identical input alphabet, then C(M)=C(N).

  • If N is a subsemiautomaton of M, then C(N) is a homomorphic imagePlanetmathPlanetmathPlanetmath of a submonoid of C(M).

  • If N is a homomorphic image of M, so is C(N) a homomorphic image of C(M).


  • 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
  • 2 M. Ito, Algebraic Theory of Automata and LanguagesPlanetmathPlanetmath, World Scientific, Singapore (2004).
Title characteristic monoid
Canonical name CharacteristicMonoid
Date of creation 2013-03-22 19:01:10
Last modified on 2013-03-22 19:01:10
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 68Q70
Classification msc 20M35
Classification msc 03D05
Classification msc 68Q45