On the complexity of iterated shuffle
type: Item
instance of: scholarly article
title: On the complexity of iterated shuffle
zbMATH Open document ID: 0549.68039
DOI: 10.1016/0022-0000(84)90018-7
author: Manfred K. Warmuth
author: David Haussler
published in: Journal of Computer and System Sciences
publication date: 1984-01-01T00:00:00Z
review text: It is demonstrated that the following problems are NP complete: (1) Given words w and \(w_ 1,w_ 2,...,w_ n,\) is w in the shuffle of \(w_ 1,w_ 2,...,w_ n?\) (2) Given words w and v, is w in the iterated shuffle of v? From these results we show that the languages \(\{{\$}wc\!| w^ R:w\in\{a,b\}^*\}^{\odot}, \cup_{w\in\{a,b\}^*}({\$}w)^{\odot}, \{ab^ ncde^ nf:n\geq 0\}^{\odot},\) and \(\{a^{n+1}b^ nc^ nf^ n:n\geq 0\}^{\odot}\) are NP complete, where \(\odot\) denotes the iterated shuffle. By representing these languages in various ways using the operations shuffle, iterated shuffle, union, concatenation, intersection, intersection with a regular set, non-erasing homomorphism and inverse homomorphism, results on the complexity of language classes generated using various subsets of these operations are obtained. Finally, it is shown that the iterated shuffle of a regular set can be recognized in deterministic polynomial time. Further results: We can show that \(\{ab^ nc)^ 2:n\geq 0\}^{\odot}\) and \(\{a(a^ nb^ n)^ 2:n\geq 0\}^{\odot}\) are NP-complete.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3876593
zbMATH Keywords: NP complete
zbMATH Keywords: iterated shuffle
zbMATH Keywords: complexity of language classes
zbMATH Keywords: regular set
MaRDI profile type: Publication
full work available at URL: 0022-0000(84)90018-7
OpenAlex ID: W2036157680
cites work: Relations of flow languages to Petri net languages
cites work: Complexity Results for Multiprocessor Scheduling under Resource Constraints
cites work: Shuffle languages, Petri nets, and context-sensitive grammars
cites work: The power of synchronizing operations on strings
cites work: Extending regular expressions with iterated shuffle
cites work: Q4140399
cites work: Software Descriptions with Flow Expressions
cites work: Q3883468
Recommended article: On the complexity and decidability of some problems involving shuffle
Recommended article: On the round complexity of the shuffle model
Recommended article: Circuit Complexity of Shuffle
Recommended article: Q5003075
Recommended article: Q4783736
Recommended article: Sometimes-Recurse Shuffle
Recommended article: Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
Recommended article: On the Power of the Randomized Iterate
description: scientific article; zbMATH DE number 3876593