Accession Number : AD0703654

Title :   ON THE UNRECOGNIZABILITY OF SETS.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CALIF

Personal Author(s) : Knode,Ronald Barry

Report Date : JUN 1969

Pagination or Media Count : 42

Abstract : Many of the results achieved concerning regularity or non-regularity of sets have been done in the context of equivalence relations of finite index and a fundamental lemma concerning the way certain input can be separated. Recently Marvin Minsky and Seymour Papert developed a set of criteria for non-regularity based on a limiting quantity which seems intuitively to represent the portion or percentage of strings that are in the regular set. In this paper we define for regular sets, in terms of natural Markov processes, another quantity, p(A), which, generally speaking, again represents a kind of percentage of strings in the regular set and show that, when Minsky's limits exist, these two quantities agree. From the quantity developed in this paper, however, more information can be gathered concerning the machine which recognizes the regular set (and hence information about the regular set itself) than can be gathered from Minsky's criteria. Also described is a special machine which gives an upper bound for the growth rate of sets recognizable by a certain type of automaton. Finally it is shown that the set of well-formed trees written as strings is not a regular set. (Author)

Descriptors :   (*DIGITAL COMPUTERS, MATHEMATICAL MODELS), (*SET THEORY, AUTOMATA), STOCHASTIC PROCESSES, MEASURE THEORY, GRAPHICS, THEOREMS, THESES

Subject Categories : Statistics and Probability
      Computer Hardware
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE