A Medvedev Characterization of Sets Recognized by Generalized Finite Automata.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1971
- Accession Number
- AD0722330
Entities
People
- Oliver L. Costich
Organizations
- University of Iowa