The Magic Number Problem for Subregular Language Families

Details The Magic Number Problem for Subregular Language Families The Magic Number Problem for Subregular Language Families

2010-08-10

arxiv.org/abs/1008.1653v1

EPTCS 31, 2010, pp. 110-119

Computer Science

Formal Languages and Automata Theory

In Proceedings DCFS 2010, arXiv:1008.1270

Scientific paper

10.4204/EPTCS.31.13

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 (DFA) has alpha states, for all n and alpha satisfying n less or equal to alpha less or equal to exp(2,n). A number alpha not satisfying this condition is called a magic number (for n). It was shown in [11] that no magic numbers exist for general regular languages, while in [5] trivial and non-trivial magic numbers for unary regular languages were identified. We obtain similar results for automata accepting subregular languages like, for example, combinational languages, star-free, 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.

Affiliated with

Also associated with

No associations

Rating

The Magic Number Problem for Subregular Language Families does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Magic Number Problem for Subregular Language Families, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Magic Number Problem for Subregular Language Families will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-583266