Shuffle languages are in P
From MaRDI portal
Publication:1589415
DOI10.1016/S0304-3975(99)00109-7zbMATH Open0952.68079WikidataQ127186276 ScholiaQ127186276MaRDI QIDQ1589415FDOQ1589415
Authors: Joanna Jȩdrzejowicz, Andrzej Szepietowski 
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
- scientific article; zbMATH DE number 897900
- Shuffle on positive varieties of languages
- Shuffle-based multilanguages
- Shuffle on array languages generated by array grammars
- Languages under concatenation and shuffling
- scientific article; zbMATH DE number 1972802
- Shuffled languages -- representation and recognition
- A hierarchy of languages with catenation and shuffle
- Recognizing Shuffled Languages
- On a hierarchy of languages with catenation and shuffle
Cites Work
- Title not available (Why is that?)
- Concurrent regular expressions and their relationship to Petri nets
- Software Descriptions with Flow Expressions
- Extending regular expressions with iterated shuffle
- The power of synchronizing operations on strings
- On the enlargement of the class of regular languages by the shuffle closure
- Nesting of shuffle closure is important
Cited In (20)
- Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
- On the complexity and decidability of some problems involving shuffle
- Jumping finite automata: characterizations and complexity
- Circuit complexity of shuffle
- Title not available (Why is that?)
- Extending regular expressions with iterated shuffle
- On Shuffle Ideals
- String shuffle: circuits and graphs
- On the expressive power of the shuffle operator matched with intersection by regular sets
- Recognizing Shuffled Languages
- SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
- Unshuffling a square is NP-hard
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- Characterization and complexity results on jumping finite automata
- Structural properties of shuffle automata
- The commutative closure of shuffle languages over group languages is regular
- Counter machines, Petri nets, and consensual computation
- Shuffled languages -- representation and recognition
- Shuffle-based multilanguages
- Tree shuffle
This page was built for publication: Shuffle languages are in P
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1589415)
