String shuffle: circuits and graphs
DOI10.1016/J.JDA.2015.01.003zbMATH Open1322.68295OpenAlexW1987706313MaRDI QIDQ2018545FDOQ2018545
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
Recommendations
- Shuffles and concatenations in the construction of graphs
- Circuit complexity of shuffle
- scientific article; zbMATH DE number 3981198
- String decompositions of graphs
- String graphs and incomparability graphs
- String graphs and incomparability graphs
- Index-Shuffle Graphs
- String graphs and separators
- Shuffle operations on discrete paths
- Graphs, strings, and actions
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)
Cites Work
- Title not available (Why is that?)
- The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- A taxonomy of problems with fast parallel algorithms
- Parity, circuits, and the polynomial-time hierarchy
- Unambiguous functions in logarithmic space
- Making Nondeterminism Unambiguous
- Shuffle languages are in P
- Shuffle languages, Petri nets, and context-sensitive grammars
- Software Descriptions with Flow Expressions
- Mappings of languages by two-tape devices
- 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
- Unshuffling a square is NP-hard
- On Recognizing Words That Are Squares for the Shuffle Product
- Directed Planar Reachability Is in Unambiguous Log-Space
- Properties that characterize LOGCFL
- On the Tape Complexity of Deterministic Context-Free Languages
- Title not available (Why is that?)
- Circuit Complexity of Shuffle
- On the computational complexity of a merge recognition problem
- An approach to software system modelling and analysis
- An algorithm for a merge recognition problem
- A P-complete language describable with iterated shuffle
- On the expressive power of the shuffle operator matched with intersection by regular sets
- Structural properties of shuffle automata
- Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
Cited In (2)
This page was built for publication: String shuffle: circuits and graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018545)
