Talk:Star height problem

Latest comment: 12 years ago by Howard McCay in topic Merger

"The answer is yes." The answer to what is yes?


"The answer to all questions is yes" - The answer to all three questions, or all two questions? If this is just referring to the last two questions, it makes more sense to me, but then it should say "The answer to *both* questions is yes". A5 00:24, 13 Sep 2004 (UTC)


What is the non-elementary complexity of the algorithm? Is it possible to elaborate on this? Absolt (talk) 14:51, 20 July 2008 (UTC)Reply

I am not aware of an explicit upper bound for the running time of Hashiguchi's algorithm ("non-elementary" gives a lower bound on the running time; I suppose you know what non-elementary means; otherwise, see ELEMENTARY). It is extremely impractical anyway: An informal discussion, including some concrete numbers for a small example, is found at page 2, in this work:
S. Lombardy, J. Sakarovitch:"Star Height of Reversible Languages and Universal Automata", LATIN 2002.
Hermel (talk) 11:42, 24 July 2008 (UTC)Reply

Merger

edit

I suggest merging this with Star heightZarboublian (talk) 06:19, 27 April 2010 (UTC)Reply

Then you will have to merge also the article on generalized star height problem into star height. I think that there is enough material worth including in wikipedia that each topic deserves its own article. And in my opinion, mixing the star height problem and the generalized star height problem in a single article leads to confusion. The problems are superficially similar, but are of a fundamentally different nature.  Hermel (talk) 06:45, 20 May 2010 (UTC)Reply
Are these problems not addressed in the Eggan's theorem and Generalized star height sections of the Star height article?  The generalized star height problem as of this writing contains very little information, so I don't see any problem with merging these three articles.  Howard McCay (talk) 04:40, 24 July 2012 (UTC)Reply