Generalized Cascade Decompositions of Automata

Publisher Website
Google Scholar
Abstract
Incompletely specified (Mealy type) sequential machines and their generalizations to infinite machines are discussed. Convenient algebraic techniques for the study of such machines are introduced. These techniques are based on binary relations and on an extension of the usual concept of homomorphism to multivalued mappings. The first part of the paper gives a short, unified introduction to the algebraic theory of partial automata. The second part unifies and extends the algebraic approach to generalized cascade decompositions which combine conventional decomposition techniques with state-splitting procedures. The relationship between such generalized decompositions and state reductions of automata is investigated.

This publication has 3 references indexed in Scilit: