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, 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, Minimum-cost delegation in service composition, 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