star height problem

The star-height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions with a limited nesting depth of Kleene stars. 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 25 years until it was solved by Kosaburo Hashiguchi. The answer to all questions is yes: Hashiguchi published an algorithm to determine an expression's star height in 1988. Also see generalized star height problem.

References

Kosaburo Hashiguchi, Regular languages of star height one, Information and Control, 53: 199-210, 1982
Kosaburo Hashiguchi, Algorithms for Determining Relative Star Height and Star Height, Inf. Comput. 78(2): 124-169, 1988

<< Previous

Word Browser

Next >>

skeleton
sarah michelle gellar
sonic screwdriver
slide guitar
steel guitar
sunspot
sicily
walk (sheepshead)
leasters (sheepshead)
schmear (sheepshead)
schneider (sheepshead)

long (sheepshead)
blind (sheepshead)
variations of sheepshead
stanley milgram
senegal river
subset
stonehenge
sima qian
structural geology
sperm
samuel beckett

sam peckinpah
shanghai
sinai peninsula
spy fiction
william crookes
september 16
september 23
symbolic logic
sonny bono
single market
special administrative region

superstring theory
seattle mariners
source code
space
cuisine of spain
santiago de compostela
salamanca
sailing
slashdot effect
simple mail transfer protocol
shuttlecock