On the complexity of iterated shuffle

DOI10.1016/0022-0000(84)90018-7zbMath0549.68039OpenAlexW2036157680MaRDI QIDQ800086

David Haussler, Manfred K. Warmuth

Publication date: 1984

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(84)90018-7

zbMATH Keywords

NP completeregular setcomplexity of language classesiterated shuffle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Minimum-cost delegation in service composition ⋮ The Frobenius problem for the shuffle operation ⋮ The complexity of PDL with interleaving ⋮ Unshuffling a square is NP-hard ⋮ Shuffled languages -- representation and recognition ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ NWP-miner: nonoverlapping weak-gap sequential pattern mining ⋮ Subsequence covers of words ⋮ Unnamed Item ⋮ On the expressive power of the shuffle operator matched with intersection by regular sets ⋮ On recognising words that are squares for the shuffle product ⋮ Infinite hierarchy of shuffle expressions over a finite alphabet ⋮ Algorithmic and algebraic aspects of unshuffling permutations ⋮ A P-complete language describable with iterated shuffle ⋮ A Note on Multidimensional Dyck Languages ⋮ String shuffle: circuits and graphs ⋮ COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA ⋮ Recognizing binary shuffle squares is \textsf{NP}-hard ⋮ The Shuffle Product: New Research Directions ⋮ Hardness of equivalence checking for composed finite-state systems ⋮ Tight Bounds on the Descriptional Complexity of Regular Expressions ⋮ Lower Space Bounds for Accepting Shuffle Languages ⋮ Reconstructing a history of recombinations from a set of sequences ⋮ Computing possible and certain answers over order-incomplete data ⋮ Extending regular expressions with iterated shuffle ⋮ Another generalization of Higman's well quasi order result on \(\Sigma ^*\)

Cites Work

• Unnamed Item
• Unnamed Item
• Extending regular expressions with iterated shuffle
• Relations of flow languages to Petri net languages
• The power of synchronizing operations on strings
• Shuffle languages, Petri nets, and context-sensitive grammars
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Software Descriptions with Flow Expressions