Transition graphs and the star height problem
- 1 October 1968
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 383-394
- https://doi.org/10.1109/swat.1968.39
Abstract
This paper deals with cycle rank of finite transition graphs and its relation to the (restricted) star height of regular events. Rank-non-increasing transformations on transition graphs are studied. It is proved that for every transition graph G there exists an equivalent reduced non-deterministic state graph G', having no more nodes than G and no higher rank. This result yields a stronger version of Eggan's theorem on star height. Some new notions concerning non-deterministic state graphs are then introduced and utilized for developing a proof technique for establishing the star height of regular events. Results on the star height of events recognized by reset-free state graphs are also obtained.Keywords
This publication has 9 references indexed in Scilit:
- On Decompositions of Regular EventsJournal of the ACM, 1969
- The loop complexity of pure-group eventsInformation and Control, 1967
- Roots of Star EventsJournal of the ACM, 1967
- On the star height of regular eventsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1967
- 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
- Finite Automata and Their Decision ProblemsIBM Journal of Research and Development, 1959