State Complexity: Recent Results and Open Problems

Issue title: Contagious Creativity – In Honor of the 80th Birthday of Professor Solomon Marcus

Article type: Research Article

Authors: Yu, Sheng

Affiliations: Department of Computer Science, University of Western Ontario, London, Ontario, Canada N6A 5B7. [email protected]

Note: [] Address for correspondence: Department of Computer Science, University of Western Ontario, London, Ontario N6A 5B7, Canada

Abstract: 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.

Keywords: State complexity, regular languages, finite languages, finite automata

Journal: Fundamenta Informaticae, vol. 64, no. 1-4, pp. 471-480, 2005