String shuffle: circuits and graphs
type: Item
instance of: scholarly article
title: String shuffle: circuits and graphs
zbMATH Open document ID: 1322.68295
author: Neerja Mhaskar
author: Michael Soltys
published in: Journal of Discrete Algorithms
publication date: 2015-03-24T00:00:00Z
Mathematics Subject Classification ID: 68W32
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 6419174
zbMATH Keywords: string shuffle
zbMATH Keywords: circuit complexity
zbMATH Keywords: lower bounds
zbMATH Keywords: anti-Monge condition
MaRDI profile type: Publication
full work available at URL: j.jda.2015.01.003
OpenAlex ID: W1987706313
cites work: Planar and grid graph reachability problems
cites work: Directed Planar Reachability Is in Unambiguous Log-Space
cites work: The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
cites work: Unshuffling a square is NP-hard
cites work: Linear and Time Minimum-Cost Matching Algorithms for Quasi-Convex Tours
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Mappings of languages by two-tape devices
cites work: Shuffle languages, Petri nets, and context-sensitive grammars
cites work: Tight Bounds on the Descriptional Complexity of Regular Expressions
cites work: Unambiguous functions in logarithmic space
cites work: The power of synchronizing operations on strings
cites work: Extending regular expressions with iterated shuffle
cites work: Structural properties of shuffle automata
cites work: Shuffle languages are in P
cites work: On the expressive power of the shuffle operator matched with intersection by regular sets
cites work: An algorithm for a merge recognition problem
cites work: On the computational complexity of a merge recognition problem
cites work: Q4298260
cites work: Making Nondeterminism Unambiguous
cites work: An approach to software system modelling and analysis
cites work: On Recognizing Words That Are Squares for the Shuffle Product
cites work: Q4219291
cites work: Software Descriptions with Flow Expressions
cites work: A P-complete language describable with iterated shuffle
cites work: Circuit Complexity of Shuffle
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Properties that characterize LOGCFL
cites work: On the complexity of iterated shuffle
DOI: 10.1016/J.JDA.2015.01.003
Recommended article: Shuffles and concatenations in the construction of graphs
Recommended article: Circuit Complexity of Shuffle
Recommended article: Q3745859
Recommended article: String decompositions of graphs
Recommended article: String graphs and incomparability graphs
Recommended article: Index-Shuffle Graphs
Recommended article: String graphs and separators
Recommended article: Shuffle operations on discrete paths
Recommended article: Graphs, Strings, and Actions
description: scientific article; zbMATH DE number 6419174