INFINITE STRINGS OVER FINITE MACHINES.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 1970
- Accession Number
- AD0707687
Entities
People
- Harold Randall Johnson
Organizations
- University of Illinois Urbana–Champaign