Elsevier

Theoretical Computer Science

Volume 429, 20 April 2012, Pages 164-168
Theoretical Computer Science

Algebraic structures of automata

https://doi.org/10.1016/j.tcs.2011.12.035Get rights and content
Under an Elsevier user license
open archive

Abstract

To determine the structure of an automaton A, we define the layers of A, which form a poset. We show that for any finite poset P there exists an automaton whose poset of layers is isomorphic to P. All subautomata of an automaton A are characterized by the layers of A, and they form a Ps-type upper semilattice. Conversely, for any Ps-type upper semilattice L there exists an automaton whose upper semilattice of subautomata is isomorphic to L. Among the classes of automata, we consider the class of single bottom automata, and we provide the composition of a single loop automaton and a strongly connected automaton together with its automorphism group.

Keywords

Automaton
Layer of an automaton
Poset
Subautomaton
Semilattice
Single bottom automaton
Strongly connected automaton
Decomposition of an automaton
Composition of automata
Automorphism group of an automaton

Cited by (0)