Shuffled languages -- representation and recognition

DOI10.1016/J.TCS.2013.04.022MaRDI QIDQ388107zbMATH OpenOpenAlexFDO

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

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

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

• 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
• 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?)
• 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

(7)

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

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)