DEGENERATE AUTOMATA: SOME RELATIONSHIPS INVOLVING SEMIGROUP ORDER AND REGULAR EVENTS.
Abstract
This report investigates some relationships involving the order of the semi-group of an automaton and a class of automata for which this order takes on its smallest value relative to the number of states. This class, called degenerate, is a limiting class in the sense that the semi-group order of any connected machine equals the number of states if it is degenerate, and is strictly greater than the state cardinality otherwise. Further, we show by counter-example that this result does not necessarily hold for disconnected machines even when they are reduced in appropriately defined manner. The lower bound on semi-group order is strengthened in the case of strongly connected automata. It is also shown that the class of degenerate automata, as herein defined, properly includes a variety of semi-group and group type automata studied in the literature. The relevance of semi-group order to the acceptance properties of automata is suggested. In particular, the number of subclasses and the minimum lengths of strings in an acceptor class are related to the semi-group order. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1966
- Accession Number
- AD0647310
Entities
People
- Bernard Zeigler
Organizations
- University of Michigan