Shuffled languages -- representation and recognition

DOI10.1016/J.TCS.2013.04.022MaRDI QIDQ388107zbMATHOpenAlexFDO

Authors Martin Berglund, Henrik Björklund, Johanna 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)

Recommendations

• Recognizing Shuffled Languages
• On the expressive power of the shuffle operator matched with intersection by regular sets
• On shuffling a word with its letter-to-letter substitution

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2086416 (Why is no real title available?)
• scientific article; zbMATH DE number 2086614 (Why is no real title available?)
• scientific article; zbMATH DE number 1869487 (Why is no real title available?)
• scientific article; zbMATH DE number 1916664 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• An approach to software system behavior description
• Axiomatizing shuffle and concatenation in languages
• Biased Boltzmann samplers and generation of extended linear languages with shuffle
• Concurrent regular expressions and their relationship to Petri nets
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Languages generated by context-free grammars extended by type \(AB\to BA\) rules
• Mappings of languages by two-tape devices
• Nonfinite axiomatizability of the equational theory of shuffle
• ON A HIERARCHY OF PERMUTATION LANGUAGES
• On free monoids partially ordered by embedding
• On the complexity of iterated shuffle
• On the shuffle automaton size for words
• Operational state complexity of prefix-free regular languages
• Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
• Orthogonal concatenation: language equations and state complexity
• Parametrized complexity theory.
• Quotient Complexity of Ideal Languages
• Shuffle languages are in P
• Shuffle languages, Petri nets, and context-sensitive grammars
• Shuffle on positive varieties of languages
• Shuffle on trajectories: Syntactic constraints
• Software Descriptions with Flow Expressions
• The expressive power of the shuffle product
• Very special languages and representations of recursively enumerable languages via computation histories
• Visibly pushdown languages

Cited in

(6)

• Recognizing Shuffled Languages
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Shuffle languages are in P
• Counter machines, Petri nets, and consensual computation
• scientific article; zbMATH DE number 897900 (Why is no real title available?)
• On the membership problem of permutation grammars -- a direct proof of NP-completeness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q388107)