×

State complexity: recent results and open problems. (English) Zbl 1102.68076

Summary: In this paper, we summarize recent results and progress in state complexity research. We analyze why many basic state complexity problems were not solved earlier, in the sixties and seventies. We also suggest several future directions for this area of research.

MSC:

68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: Link