On the complexity of iterated shuffle

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

Manfred K. Warmuth, David Haussler

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 complete; regular set; complexity of language classes; iterated shuffle

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68Q45: Formal languages and automata

Related Items

On the expressive power of the shuffle operator matched with intersection by regular sets, Lower Space Bounds for Accepting Shuffle Languages, A Note on Multidimensional Dyck Languages, Shuffled languages -- representation and recognition, Infinite hierarchy of shuffle expressions over a finite alphabet, Hardness of equivalence checking for composed finite-state systems, Extending regular expressions with iterated shuffle, Another generalization of Higman's well quasi order result on \(\Sigma ^*\), A P-complete language describable with iterated shuffle, Reconstructing a history of recombinations from a set of sequences, The complexity of PDL with interleaving, String shuffle: circuits and graphs, Minimum-cost delegation in service composition, Unshuffling a square is NP-hard, COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA, Tight Bounds on the Descriptional Complexity of Regular Expressions

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