Shuffle languages are in P
From MaRDI portal
Publication:1589415
DOI10.1016/S0304-3975(99)00109-7zbMath0952.68079WikidataQ127186276 ScholiaQ127186276MaRDI QIDQ1589415
Andrzej Szepietowski, Joanna Jȩdrzejowicz
Publication date: 12 December 2000
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (13)
Unshuffling a square is NP-hard ⋮ Shuffled languages -- representation and recognition ⋮ Tree shuffle ⋮ Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking ⋮ Jumping Finite Automata: Characterizations and Complexity ⋮ Regularity Conditions for Iterated Shuffle on Commutative Regular Languages ⋮ On the expressive power of the shuffle operator matched with intersection by regular sets ⋮ On the complexity and decidability of some problems involving shuffle ⋮ Counter machines, Petri nets, and consensual computation ⋮ SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES ⋮ String shuffle: circuits and graphs ⋮ The commutative closure of shuffle languages over group languages is regular ⋮ Characterization and complexity results on jumping finite automata
Cites Work
- Unnamed Item
- On the enlargement of the class of regular languages by the shuffle closure
- Extending regular expressions with iterated shuffle
- Nesting of shuffle closure is important
- The power of synchronizing operations on strings
- Concurrent regular expressions and their relationship to Petri nets
- Software Descriptions with Flow Expressions
This page was built for publication: Shuffle languages are in P
