State Complexity of Shuffle on Trajectories
Michael Domaratzki, Kai Salomaa · 2004
It is easy to get an upper bound for the state complexity of shuffle on trajectories that generalizes the bound for unrestricted shuffle. We establish improved bounds for slender trajectories, that is, trajectories which have only a constant number of strings of a given length. For trajectories with USL-index 1 (or 1-thin trajectories, those with only one string of each length) we obtain an asymptotically optimal lower bound when the state complexity of the trajectory grows with respect to the state complexity of the component languages. Some estimations are improved by considering nondeterministic state complexity.