A Medvedev Characterization of Sets Recognized by Generalized Finite Automata.
IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Pagination or Media Count:
In 1956, I. T. Medvedev gave a characterization of the sets definable by finite state acceptors in terms of sets generated from a class of primitive sets by applications of a class of primitive operations. The purpose of this paper is to demonstrate that Medvedevs characterization can be extended to sets defined by generalized finite automata tree automata. In addition it is noted that the classes of primitives required is in fact smaller than those of Medvedev. A self-contained proof of the characterization for regular sets using the smaller classes of primitives is given. Author
- Theoretical Mathematics