On the Complexity and Decidability of Some Problems Involving Shuffle

Joey Eremondi; Oscar H. Ibarra; Ian McQuillan

doi:10.1016/j.ic.2017.09.002

paper

On the Complexity and Decidability of Some Problems Involving Shuffle

arXiv:1606.01199 · doi:10.1016/j.ic.2017.09.002

Abstract

The complexity and decidability of various decision problems involving the shuffle operation are studied. The following three problems are all shown to be $N P$ -complete: given a nondeterministic finite automaton (NFA) $M$ , and two words $u$ and $v$ , is $L (M)$ not a subset of $u$ shuffled with $v$ , is $u$ shuffled with $v$ not a subset of $L (M)$ , and is $L (M)$ not equal to $u$ shuffled with $v$ ? It is also shown that there is a polynomial-time algorithm to determine, for $N F A$ s $M_{1}, M_{2}$ and a deterministic pushdown automaton $M_{3}$ , whether $L (M_{1})$ shuffled with $L (M_{2})$ is a subset of $L (M_{3})$ . The same is true when $M_{1}, M_{2}, M_{3}$ are one-way nondeterministic $l$ -reversal-bounded $k$ -counter machines, with $M_{3}$ being deterministic. Other decidability and complexity results are presented for testing whether given languages $L_{1}, L_{2}$ and $R$ from various languages families satisfy $L_{1}$ shuffled with $L_{2}$ is a subset of $R$ , and $R$ is a subset of $L_{1}$ shuffled with $L_{2}$ . Several closure results on shuffle are also shown.

Preprint submitted to Information and Computation

References in corpus (1)

Commutative Languages and their Composition by Consensual Methods

On the Complexity and Decidability of Some Problems Involving Shuffle

Abstract

References in corpus (1)

Cited by in corpus (3)