Shuffle languages are in P
From MaRDI portal
In this paper we show that shuffle languages are contained in one-way-NSPACE\((\log n)\) thus in P. We consider the class of shuffle languages which emerges from the class of finite languages through regular operations (union, concatenation, Kleene star) and shuffle operations (shuffle and shuffle closure). For every shuffle expression \(E\) we construct a shuffle automaton which accepts the language generated by \(E\) and we show that the automaton can be simulated by a one-way nondeterministic Turing machine in logarithmic space.
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
- Concurrent regular expressions and their relationship to Petri nets
- Extending regular expressions with iterated shuffle
- scientific article; zbMATH DE number 3311755 (Why is no real title available?)
- Nesting of shuffle closure is important
- On the enlargement of the class of regular languages by the shuffle closure
- Software Descriptions with Flow Expressions
- The power of synchronizing operations on strings
Cited in
(23)- Extending regular expressions with iterated shuffle
- Shuffle-based multilanguages
- Structural properties of shuffle automata
- String shuffle: circuits and graphs
- The commutative closure of shuffle languages over group languages is regular
- Characterization and complexity results on jumping finite automata
- Unshuffling a square is NP-hard
- Circuit complexity of shuffle
- Jumping finite automata: characterizations and complexity
- Recognizing Shuffled Languages
- SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
- scientific article; zbMATH DE number 992018 (Why is no real title available?)
- Shuffled languages -- representation and recognition
- Tree shuffle
- Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
- Languages under concatenation and shuffling
- On the expressive power of the shuffle operator matched with intersection by regular sets
- On Shuffle Ideals
- Lower Space Bounds for Accepting Shuffle Languages
- scientific article; zbMATH DE number 897900 (Why is no real title available?)
- Counter machines, Petri nets, and consensual computation
- Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
- The n-ary initial literal and literal 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)
