
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 nonregularity 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 nonregularity 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 wellformed 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