INFINITE STRINGS OVER FINITE MACHINES

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 thes...

Full description

Saved in:
Bibliographic Details
Main Author: Johnson,Harold Randall
Format: Report
Language:English
Subjects:
AUTOMATA
Bionics
Computer Hardware
COMPUTER LOGIC
DIGITAL COMPUTERS
FINITE STATE MACHINES
SET THEORY
THEOREMS
THEORY
THESES
TOPOLOGY
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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)