Shuffled languages -- representation and recognition
From MaRDI portal
Publication:388107
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
Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
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
