On the complexity and decidability of some problems involving shuffle

DOI10.1016/j.ic.2017.09.002zbMath1390.68392arXiv1606.01199OpenAlexW1081471053MaRDI QIDQ1706154

Ian McQuillan, Oscar H. Ibarra, Joey Eremondi

Publication date: 21 March 2018

Published in: Information and Computation, Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1606.01199

zbMATH Keywords

shuffledeterminismstringscommutativitycounter machinesreversal-boundspushdown machinesautomata and logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Insertion operations on deterministic reversal-bounded counter machines ⋮ On finite-index indexed grammars and their restrictions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The effect of end-markers on counter machines and commutativity
• Algorithmic decomposition of shuffle on words
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• On the uniqueness of shuffle on words and finite languages
• The complexity of decision problems for finite-turn multicounter machines
• Reversal-bounded multipushdown machines
• Economy of description by parsers, DPDA's, and PDA's
• On language equations with invertible operations
• Shuffle languages are in P
• Shuffle factorization is unique
• Aspects of shuffle and deletion on trajectories
• On properties of bond-free DNA languages
• Some decision problems concerning semilinearity and commutation.
• Deletion operations on deterministic families of automata
• Insertion operations on deterministic reversal-bounded counter machines
• Unshuffling a square is NP-hard
• On Comparing Deterministic Finite Automata and the Shuffle of Words
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
• Reversal-Bounded Multicounter Machines and Their Decision Problems
• On Recognizing Words That Are Squares for the Shuffle Product
• Mappings of languages by two-tape devices
• Implementation and Application of Automata
• Automata with Reversal-Bounded Counters: A Survey

This page was built for publication: On the complexity and decidability of some problems involving shuffle