String shuffle: circuits and graphs

DOI10.1016/J.JDA.2015.01.003MaRDI QIDQ2018545zbMATH OpenOpenAlexFDO

Authors Neerja Mhaskar, Michael Soltys

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

zbMATH Keywords

lower boundscircuit complexityanti-Monge conditionstring shuffle

Mathematics Subject Classification ID

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)

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

Cites work

• scientific article; zbMATH DE number 1220163 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• A P-complete language describable with iterated shuffle
• A taxonomy of problems with fast parallel algorithms
• An algorithm for a merge recognition problem
• An approach to software system modelling and analysis
• Circuit complexity of shuffle
• Directed planar reachability is in unambiguous log-space
• Extending regular expressions with iterated shuffle
• Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
• Making Nondeterminism Unambiguous
• Mappings of languages by two-tape devices
• On recognizing words that are squares for the shuffle product
• On the Tape Complexity of Deterministic Context-Free Languages
• On the complexity of iterated shuffle
• On the computational complexity of a merge recognition problem
• On the expressive power of the shuffle operator matched with intersection by regular sets
• Parity, circuits, and the polynomial-time hierarchy
• Planar and grid graph reachability problems
• Properties that characterize LOGCFL
• Shuffle languages are in P
• Shuffle languages, Petri nets, and context-sensitive grammars
• Software Descriptions with Flow Expressions
• Structural properties of shuffle automata
• The power of synchronizing operations on strings
• 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
• Unambiguous functions in logarithmic space
• Unshuffling a square is NP-hard

Cited in

(5)

• Circuit complexity of shuffle
• Unshuffling permutations: trivial bijections and compositions
• A constant time string shuffle algorithm on reconfigurable meshes
• Unshuffling a square is NP-hard
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages

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)