LATTICE STRUCTURES OF AUTOMATA

Abstract

Structures and the number of subautomata of a finite automaton are investigated. It is shown that the set of all subautomata of a finite automa- ton A is upper semilattice. We give conditions which allow us to determine whether for a finite upper semilattice (L, ≤) there exists an automaton A such that the set of all subautomata of A under set inclusion is isomorphic to (L, ≤). Examples illustrating the results are presented.