Journal article

Publication year: 2012

Pages: 115-131

Journal: International Journal of Foundations of Computer Science

Volume number: 23

Issue number: 1

ISSN: 0129-0541

DOI Link: https://doi.org/10.1142/S0129054112400084

Publisher: World Scientific Publishing

Abstract: 
We investigate the magic number problem, that is, the question whether there exists a minimal n-state nondeterministic finite automaton (NFA) whose equivalent minimal deterministic finite automaton (DEA) has a states, for all n and alpha satisfying n <= alpha <= 2(n). A number is not satisfying this condition is called a magic number (for m). It was shown that no magic numbers exist for general regular languages, whereas trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, star-free languages, prefix-, suffix-, and infix-closed languages, and prefix-, suffix-, and infix-free languages, showing that there are only trivial magic numbers, when they exist. For finite languages we obtain some partial results showing that certain numbers are non-magic.

Harvard Citation style: Holzer, M., Jakobi, S. and Kutrib, M. (2012) THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES, International Journal of Foundations of Computer Science, 23(1), pp. 115-131. https://doi.org/10.1142/S0129054112400084

APA Citation style: Holzer, M., Jakobi, S., & Kutrib, M. (2012). THE MAGIC NUMBER PROBLEM FOR SUBREGULAR LANGUAGE FAMILIES. International Journal of Foundations of Computer Science. 23(1), 115-131. https://doi.org/10.1142/S0129054112400084