Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6873879 | Information and Computation | 2018 | 11 Pages |
Abstract
The complexity and decidability of various decision problems involving the shuffle operation (denoted by ⧢) are studied. The following three problems are all shown to be NP-complete: given a nondeterministic finite automaton (NFA) M, and two words u and v, is L(M)âu⧢v, is u⧢vâL(M), and is L(M)â u⧢v? It is also shown that there is a polynomial-time algorithm to determine, for NFAs M1,M2, and a deterministic pushdown automaton M3, whether L(M1)⧢L(M2)âL(M3). The same is true when M1,M2,M3 are one-way nondeterministic l-reversal-bounded k-counter machines, with M3 being deterministic. Other decidability and complexity results are presented for testing whether given languages L1,L2, and R from various languages families satisfy L1⧢L2âR, and RâL1⧢L2. Several closure results on shuffle are also shown.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Joey Eremondi, Oscar H. Ibarra, Ian McQuillan,