subsemiautomaton


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 former.

Definition

A semiautomaton N=(T,Γ,γ) is said to be a subsemiautomaton of a semiautomaton M=(S,Σ,δ) if

TS,ΓΣ,and  γδ.

The last inclusion means the following: γ(s,a)=δ(s,a) for all (s,a)T×Γ. We write NM when N is a subsemiautomaton of M.

A subsemiautomaton N of M is said to be proper if NM, and is written N<M.

Examples. Let M=(S,Σ,δ) be a semiautomaton.

  • M can be represented by its state diagramMathworldPlanetmath, which is just a directed graphMathworldPlanetmath. Any strongly connected componentMathworldPlanetmath of the state diagram represents a subsemiautomaton of M, characterized as a semiautomaton (S,Σ,δ) such that any state in S can be reached from any other state in S. In other words, for any s,tS, there is a word u over Σ such that either tδ(s,u), where δ is the restrictionPlanetmathPlanetmathPlanetmath of δ to S×Σ. A semiautomaton whose state diagram is strongly connected is said to be strongly connected.

  • Suppose M is strongly connected. Then M has no proper subsemiautomaton whose input alphabet is equal to the input alphabet of M. In other words, if N=(T,Σ,γ)M, then N=M. However, proper subsemiautomata of M exist if we take N=(T,Γ,γ) for any proper subsetMathworldPlanetmathPlanetmath Γ of Σ, provided that |Σ|2. In this case, γ is just the restriction of δ to the set T×Γ.

  • On the other hand, if Σ is a singleton, and M is strongly connected, then no proper subsemiautomata of M exist. Notice that if the transition function δ is single valued, then it is just a permutationMathworldPlanetmath on S of order |S|.

Specializations to Other Machines

Computing devices derived from semiautomata such as automata and state-output machines may too be considered as algebrasMathworldPlanetmath. We record the definitions of subalgebras of these objects here.

Note: the following notations are used: 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). A=(A,I,F) is a subautomaton of B=(B,J,G) if

AB,IJ,and  FG.

Definition (state-output machine). M=(M,Δ,λ) is a submachine of N=(N,Ω,π) if

MN,ΔΩ,and λ is the restriction of π to S×Σ,

where S and Σ are the state and input alphabets of M.

References

  • 1 A. Ginzburg, Algebraic Theory of Automata, Academic Press (1968).
Title subsemiautomaton
Canonical name Subsemiautomaton
Date of creation 2013-03-22 19:01:03
Last modified on 2013-03-22 19:01:03
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 20M35
Classification msc 03D05
Classification msc 68Q45
Classification msc 68Q70
Defines strongly connected semiautomaton
Defines subsemiautomata
Defines subautomaton
Defines submachine