semiautomaton homomorphism


Just like groups and rings, a semiautomaton can be viewed as an algebraic structurePlanetmathPlanetmath. As such, one may define algebraic constructs such as subalgebrasPlanetmathPlanetmathPlanetmath and homomorphismsMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath. In this entry, we will briefly discuss the later.

Definition

A homomorphism from a semiautomaton M=(S,Σ,δ) to a semiautomaton N=(T,Γ,γ) is a pair of maps h:=(f:ST,g:ΣΓ) such that

f(δ(s,a))=γ(f(s),g(a))

The image of the homomorphism h is the subsemiautomaton h(M):=(f(S),g(Σ),γ) of N, where γ is the restrictionPlanetmathPlanetmath of γ to f(S)×g(Σ), also known as the homomorphic image of M under h.

In general, a semiautomaton N is said to be a homomorphic image of a semiautomaton M, if there is a homomorphism h such that h(M)=N.

When comparing two semiautomata M,N, it is customary to identify the two corresponding input alphabets Σ,Γ, especially when one wants to study the interaction between the states of M and the states of N. This can be done by taking Δ:=ΣΓ, and extend the corresponding transition functions so that they are identitiesPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath on the extended portions of the input alphabets. Call the extended semiautomata M,N.

If h:MN is a homomorphism, then h:MN extends h in a natural way: f=f, and g:ΔΔ given by g(a)=g(a) if aΣ, and g(a)=a if aΓ-Σ. Routine verification shows that h is indeed a homomorphism: if aΣ,

f(δ(s,a))=f(δ(s,a))=f(δ(s,a))=γ(f(s),g(a))=γ(f(s),g(a))=γ(f(s),g(a)),

and if aΓ-Σ, then

f(δ(s,a))=f(δ(s,a))=f(s)=γ(f(s),a)=γ(f(s),a)=γ(f(s),g(a)).

A homomorphism h=(f,g):MN is an isomorphismMathworldPlanetmathPlanetmath if both f and g are bijections. As discussed above, if we identify the input alphabets of M and N, and treat g as the identity map on the input alphabet, then (S,Σ,δ) and (T,Σ,γ) are isomorphic if there is a bijection f:ST such that f(δ(s,a))=γ(f(s),a).

Specializations to Other Machines

Computing devices derived from semiautomata such as automata and state-output machines may also be considered as algebrasMathworldPlanetmath. We record the definitions of homomorphisms with respect to these objects here.

We adopt the following notations: given an automaton A=(S,Σ,δ,I,F) and a state-output machine M=(S,Σ,Δ,δ,λ), let A and M be the associated semiautomaton (S,Σ,δ). So A and M may be written (A,I,F) and (M,Δ,λ) respectively.

Definition (automaton). Given automata A=(A,I,F) and B=(B,J,G). Then

h=(f,g):AB

is a homomorphism if

  • h:AB is a semiautomaton homomorphism, such that

  • f(I)J, and f(F)G.

A homomorphism h:AB is an isomorphism if h:AB is an isomorphism such that f(I)=J and f(F)=G.

Definition (state-output machine). Given state-output machines M=(M,Δ,λ) and N=(N,Ω,π). Then

ϕ=(h,k):MN

is a homomorphism if

  • h:MN is a semiautomaton homomorphism, and

  • k:ΔΩ, such that

    k(λ(s,a))=π(f(s),g(a)),

    for all (s,a)S×Σ, where S and Σ are the state and input alphabets of M.

A homomorphism ϕ:AB is an isomorphism if h:MN is an isomorphism and k is a bijection.

References

  • 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
Title semiautomaton homomorphism
Canonical name SemiautomatonHomomorphism
Date of creation 2013-03-22 19:01:07
Last modified on 2013-03-22 19:01:07
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 68Q45
Classification msc 20M35
Classification msc 03D05
Classification msc 68Q70
Defines homomorphism
Defines homomorphic image
Defines isomorphism
Defines automaton homomorphism
Defines machine homomorphism