Name
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.ic.2017.09.002 | Information and Computation |
Keywords | Field | DocType |
Automata and logic,Shuffle,Counter machines,Pushdown machines,Reversal-bounds,Determinism,Commutativity,Strings | Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Decision problem,Nondeterministic finite automaton,Nondeterministic algorithm,Deterministic pushdown automaton,Decidability,Pushdown automaton,Mathematics | Conference |
Volume | Issue | ISSN |
259 | Part | 0890-5401 |
Citations | PageRank | References |
0 | 0.34 | 23 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Joey Eremondi | 1 | 8 | 1.65 |
| Oscar H. Ibarra | 2 | 3235 | 741.44 |
| Ian McQuillan | 3 | 97 | 24.72 |