subsemiautomaton
Just like groups and rings, a semiautomaton can be viewed as an algebraic structure. As such, one may define algebraic constructs such as subalgebras and homomorphisms. In this entry, we will briefly discuss the former.
Definition
A semiautomaton is said to be a subsemiautomaton of a semiautomaton if
The last inclusion means the following: for all . We write when is a subsemiautomaton of .
A subsemiautomaton of is said to be proper if , and is written .
Examples. Let be a semiautomaton.
-
•
can be represented by its state diagram, which is just a directed graph. Any strongly connected component of the state diagram represents a subsemiautomaton of , characterized as a semiautomaton such that any state in can be reached from any other state in . In other words, for any , there is a word over such that either , where is the restriction of to . A semiautomaton whose state diagram is strongly connected is said to be strongly connected.
-
•
Suppose is strongly connected. Then has no proper subsemiautomaton whose input alphabet is equal to the input alphabet of . In other words, if , then . However, proper subsemiautomata of exist if we take for any proper subset of , provided that . In this case, is just the restriction of to the set .
-
•
On the other hand, if is a singleton, and is strongly connected, then no proper subsemiautomata of exist. Notice that if the transition function is single valued, then it is just a permutation on of order .
Specializations to Other Machines
Computing devices derived from semiautomata such as automata and state-output machines may too be considered as algebras. We record the definitions of subalgebras of these objects here.
Note: the following notations are used: given an automaton and a state-output machine , let and be the associated semiautomaton . So and may be written and respectively.
Definition (automaton). is a subautomaton of if
Definition (state-output machine). is a submachine of if
where and are the state and input alphabets of .
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 |