On the Shuffle Automaton Size for Words

Details On the Shuffle Automaton Size for Words On the Shuffle Automaton Size for Words

2009-07-29

arxiv.org/abs/0907.5111v1

EPTCS 3, 2009, pp. 79-89

Computer Science

Formal Languages and Automata Theory

Scientific paper

10.4204/EPTCS.3.7

We investigate the state size of DFAs accepting the shuffle of two words. We provide words u and v, such that the minimal DFA for u shuffled with v requires an exponential number of states. We also show some conditions for the words u and v which ensure a quadratic upper bound on the state size of u shuffled with v. Moreover, switching only two letters within one of u or v is enough to trigger the change from quadratic to exponential.

Affiliated with

Also associated with

No associations

Rating

On the Shuffle Automaton Size for Words 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 On the Shuffle Automaton Size for Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Shuffle Automaton Size for Words will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-521604