Shuffled languages -- representation and recognition

DOI10.1016/J.TCS.2013.04.022zbMath1294.68101OpenAlexW2031089507MaRDI QIDQ388107

Johanna Björklund, Martin Berglund, Henrik Björklund

Publication date: 19 December 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.04.022

zbMATH Keywords

interleavingmembership problemsshuffle languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ Counter machines, Petri nets, and consensual computation ⋮ On the Membership Problem of Permutation Grammars — A Direct Proof of NP-Completeness

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The expressive power of the shuffle product
• On the complexity of iterated shuffle
• Shuffle on trajectories: Syntactic constraints
• Nonfinite axiomatizability of the equational theory of shuffle
• Concurrent regular expressions and their relationship to Petri nets
• Axiomatizing shuffle and concatenation in languages
• Shuffle languages are in P
• Shuffle on positive varieties of languages
• Parametrized complexity theory.
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Quotient Complexity of Ideal Languages
• Visibly pushdown languages
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
• Very special languages and representations of recursively enumerable languages via computation histories
• Shuffle languages, Petri nets, and context-sensitive grammars
• Software Descriptions with Flow Expressions
• An approach to software system behavior description
• ON A HIERARCHY OF PERMUTATION LANGUAGES
• Mappings of languages by two-tape devices
• On free monoids partially ordered by embedding

This page was built for publication: Shuffled languages -- representation and recognition