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
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE