A Medvedev Characterization of Sets Recognized by Generalized Finite Automata

摘要

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 Medvedev's 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)