String shuffle: circuits and graphs
From MaRDI portal
Publication:2018545
DOI10.1016/j.jda.2015.01.003zbMath1322.68295OpenAlexW1987706313MaRDI QIDQ2018545
Michael Soltys, Neerja Mhaskar
Publication date: 24 March 2015
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jda.2015.01.003
Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Graph theory (including graph drawing) in computer science (68R10) Graph representations (geometric and intersection representations, etc.) (05C62) Algorithms on strings (68W32)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Planar and grid graph reachability problems
- On the complexity of iterated shuffle
- Extending regular expressions with iterated shuffle
- The power of synchronizing operations on strings
- An algorithm for a merge recognition problem
- On the computational complexity of a merge recognition problem
- Properties that characterize LOGCFL
- A P-complete language describable with iterated shuffle
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- Shuffle languages are in P
- Structural properties of shuffle automata
- Unshuffling a square is NP-hard
- Circuit Complexity of Shuffle
- Directed Planar Reachability Is in Unambiguous Log-Space
- Parity, circuits, and the polynomial-time hierarchy
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- A taxonomy of problems with fast parallel algorithms
- Shuffle languages, Petri nets, and context-sensitive grammars
- On the Tape Complexity of Deterministic Context-Free Languages
- Software Descriptions with Flow Expressions
- An approach to software system modelling and analysis
- On the expressive power of the shuffle operator matched with intersection by regular sets
- Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
- On Recognizing Words That Are Squares for the Shuffle Product
- Making Nondeterminism Unambiguous
- Mappings of languages by two-tape devices
This page was built for publication: String shuffle: circuits and graphs
