Transition graphs and the star height problem

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.