Accession Number:

AD0647310

Title:

DEGENERATE AUTOMATA: SOME RELATIONSHIPS INVOLVING SEMIGROUP ORDER AND REGULAR EVENTS.

Descriptive Note:

Technical rept.,

Corporate Author:

MICHIGAN UNIV ANN ARBOR COMMUNICATION SCIENCES PROGRAM

Personal Author(s):

Report Date:

1966-12-01

Pagination or Media Count:

31.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE