The Power of One Star
Philipp Weis, UMass Amherst
Tuesday 3 November 2009, 4:00 p.m.
Room 140, Computer Science Building
The generalized star height problem is a baffling open problem in formal language theory. We define generalized regular expressions in the same way as standard regular expressions, but on top of the typical concatenation, union and Kleene star operators, we also have a negation/complement operator. The generalized star height of a given regular language is the minimum nesting depth of Kleene stars needed in a generalized regular expression for that language.
All we know for sure at this point is that there are languages of generalized star height one, for example the language (aa)* of even-length strings. Over the years, several candidate languages have been conjectured to have generalized star height greater than one, but none of them have been able to live up to that claim, possibly suggesting that no such language might exist after all.
In this talk, I will give a brief overview of the generalized star height problem, present a series of four candidate languages, and show that all of these languages have generalized star height one, using tools mostly from algebraic language theory.
Last modified 30 October 2009