Specifically, is a nesting depth of more than 2 required? If so, can we determine how many are required?
This theoretical problem remained open for 30 years, to be solved by Kosaburo Hashiguchi[?] in 1983. The answer to all questions is yes: Hashiguchi published an algorithm to determine an expression's star height in 1988.
The generalized star height problem is the same problem for regular expressions that include the complement operator. This is still an open problem.
Search Encyclopedia

Featured Article
