Accession Number : AD0707687

Title :   INFINITE STRINGS OVER FINITE MACHINES.

Descriptive Note : Doctoral thesis,

Corporate Author : ILLINOIS UNIV URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Johnson,Harold Randall

Report Date : JUN 1970

Pagination or Media Count : 94

Abstract : Several authors have proposed conditions under which infinite input strings are defined by finite state machines. Corresponding to each definability condition is the class of all sets of infinite strings defined by finite machines with respect to that condition, for a fixed input alphabet. This thesis considers a family of definability conditions. This includes four countably infinite sequences of additional definability conditions. The resulting family of sets of infinite strings defined by a fixed but arbitrary machine M is partially ordered with respect to inclusion. Necessary and sufficient conditions for these inclusions to be strict are developed. Each of these conditions is decidable. Some decidability problems for individual sets are examined, and some boolean identities between such sets are presented. It is determined for which of the Boolean operations of intersection, union and complementation various of the definable classes is closed. As a result, some definable classes are shown to be equal. The family of definable classes is partially ordered with respect to inclusion. It is shown that a countable number of definable classes are distinct from those of previously prosed definability conditions. (Author)

Descriptors :   (*DIGITAL COMPUTERS, THEORY), COMPUTER LOGIC, SET THEORY, TOPOLOGY, AUTOMATA, THEOREMS, THESES

Subject Categories : Computer Hardware
      Bionics

Distribution Statement : APPROVED FOR PUBLIC RELEASE