On the State Complexity of the Shuffle of Regular Languages

Abstract: We investigate the shuffle operation on regular languages represented by complete deterministic finite automata. We prove that

f (m, n) = 2^{m n - 1} + 2^{(m - 1) (n - 1)} (2^{m - 1} - 1) (2^{n - 1} - 1)

is an upper bound on the state complexity of the shuffle of two regular languages having state complexities

m

and

n

, respectively. We also state partial results about the tightness of this bound. We show that there exist witness languages meeting the bound if

2 l e m l e 5

and

n g e 2

, and also if

m = n = 6

. Moreover, we prove that in the subset automaton of the NFA accepting the shuffle, all

2^{m n}

states can be distinguishable, and an alphabet of size three suffices for that. It follows that the bound can be met if all

f (m, n)

states are reachable. We know that an alphabet of size at least

m n

is required provided that

m, n g e 2

. The question of reachability, and hence also of the tightness of the bound

f (m, n)

in general, remains open.

Recommendations

Cites Work

Cited In (21)

Uses Software

This page was built for publication: On the State Complexity of the Shuffle of Regular Languages