Accession Number : AD0722330
Title : A Medvedev Characterization of Sets Recognized by Generalized Finite Automata.
Descriptive Note : Technical rept.,
Corporate Author : IOWA UNIV IOWA CITY DEPT OF MATHEMATICS
Personal Author(s) : Costich,Oliver L.
Report Date : MAR 1971
Pagination or Media Count : 17
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)
Descriptors : (*SET THEORY, AUTOMATA), ALGEBRA, THEOREMS
Subject Categories : Theoretical Mathematics
Distribution Statement : APPROVED FOR PUBLIC RELEASE