On the complexity of iterated shuffle
From MaRDI portal
Publication:800086
DOI10.1016/0022-0000(84)90018-7zbMATH Open0549.68039OpenAlexW2036157680MaRDI QIDQ800086FDOQ800086
Authors: 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
Recommendations
- On the round complexity of the shuffle model
- Circuit complexity of shuffle
- A combinatorial approach for the state complexity of the shuffle product
- scientific article; zbMATH DE number 1842502
- Sometimes-recurse shuffle. Almost-random permutations in logarithmic expected time
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- On the Power of the Randomized Iterate
- On the Power of the Randomized Iterate
Cites Work
- Complexity Results for Multiprocessor Scheduling under Resource Constraints
- Shuffle languages, Petri nets, and context-sensitive grammars
- Software Descriptions with Flow Expressions
- Extending regular expressions with iterated shuffle
- The power of synchronizing operations on strings
- Relations of flow languages to Petri net languages
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (35)
- On the Power of the Randomized Iterate
- Computing possible and certain answers over order-incomplete data
- New Techniques for Non-interactive Shuffle and Range Arguments
- Extending regular expressions with iterated shuffle
- On recognising words that are squares for the shuffle product
- Analysis of top to bottom-\(k\) shuffles
- An efficient pairing-based shuffle argument
- NWP-miner: nonoverlapping weak-gap sequential pattern mining
- Another generalization of Higman's well quasi order result on \(\Sigma ^*\)
- A note on multidimensional Dyck languages
- Algorithmic and algebraic aspects of unshuffling permutations
- String shuffle: circuits and graphs
- On the expressive power of the shuffle operator matched with intersection by regular sets
- Reconstructing a history of recombinations from a set of sequences
- Recognizing binary shuffle squares is \textsf{NP}-hard
- Subsequence covers of words
- Minimum-cost delegation in service composition
- Title not available (Why is that?)
- Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
- Unshuffling a square is NP-hard
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- Compressed membership problems for regular expressions and hierarchical automata
- Infinite hierarchy of shuffle expressions over a finite alphabet
- The complexity of PDL with interleaving
- Lower Space Bounds for Accepting Shuffle Languages
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- A P-complete language describable with iterated shuffle
- Shuffle algorithm for singular 2-D system
- On the itarated shuffle of some regular languages
- On the interdependence between shuffle and crossing-over operations
- The Shuffle Product: New Research Directions
- The Frobenius problem for the shuffle operation
- Hardness of equivalence checking for composed finite-state systems
- Title not available (Why is that?)
- Shuffled languages -- representation and recognition
This page was built for publication: On the complexity of iterated shuffle
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q800086)
