On the star height of regular events
- 1 January 1967
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper presents some results concerning the star height of regular events. First we consider the behavior of star height under various operations on regular events and it is proved that star height is preserved under the derivative operation. The relation of star height of a regular event to the cycle rank of the reduced state graph of the corresponding finite automaton is studied. This investigation leads to sufficient conditions for the star height to be equal to the rank of the state graph. For example, this is true for events defined by permutation automata with a single output state. Families of regular events of arbitrary star height are exhibited. Finally, some open questions posed by Eggan regarding star height and rank are answered.Keywords
This publication has 5 references indexed in Scilit:
- Roots of star events7th Annual Symposium on Switching and Automata Theory (swat 1966), 1966
- On a question of EgganInformation and Control, 1966
- Derivatives of Regular ExpressionsJournal of the ACM, 1964
- Transition graphs and the star-height of regular events.The Michigan Mathematical Journal, 1963
- Regular Expressions and State Graphs for AutomataIEEE Transactions on Electronic Computers, 1960