General properties of star height of regular events

✍ Scribed by Rina S. Cohen; J.A. Brzozowski

• Book ID: 104148016
• Publisher: Elsevier Science
• Year: 1970
• Tongue: English
• Weight: 891 KB
• Volume: 4
• Category: Article
• ISSN: 0022-0000
• DOI: 10.1016/s0022-0000(70)80024-1

✦ Synopsis

Properties of star height of regular events are investigated. It is shown that star height is preserved under such operations as taking quotients, addition or subtraction of a finite event, removal of all words beginning with a given letter, and removal of certain subsets of smaller star height. Next it is shown that there exist events of arbitrarily large star height whose union, concatenation, and star is of star height one. Also, arbitrarily large increases in star height can be obtained by using the intersection or complement operations.

In the second part of the paper a technique for establishing the star height of regular events is developed. It is shown that for every regular event R of star height n there exists a nondeterministic state graph G whose states correspond to subsets of the set of states ~) of the reduced automaton accepting R and whose cycle rank is precisely n. Unfortunately a given subset ~)' of Q may have to be repeated k times in G and no bound on k is known. Thus it is still not known whether an algorithm for determining star height exists. However, it is felt that the techniques presented here provide new insight into the problem.