Shuffle languages are in P

DOI10.1016/S0304-3975(99)00109-7MaRDI QIDQ1589415zbMATH OpenWikidataFDO

Authors Joanna Jȩdrzejowicz, Andrzej Szepietowski

Publication date 12 December 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

shufflecomplexityautomatashuffle languagespolynomial-time complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Concurrent regular expressions and their relationship to Petri nets
• Extending regular expressions with iterated shuffle
• 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

(20)

• Unshuffling a square is NP-hard
• Recognizing Shuffled Languages
• Regularity Conditions for Iterated Shuffle on Commutative Regular Languages
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• SHUFFLE DECOMPOSITIONS OF REGULAR LANGUAGES
• Shuffle-based multilanguages
• scientific article; zbMATH DE number 992018 (Why is no real title available?)
• On Shuffle Ideals
• Jumping finite automata: characterizations and complexity
• The commutative closure of shuffle languages over group languages is regular
• Circuit complexity of shuffle
• Extending regular expressions with iterated shuffle
• Shuffled languages -- representation and recognition
• On the expressive power of the shuffle operator matched with intersection by regular sets
• Structural properties of shuffle automata
• Counter machines, Petri nets, and consensual computation
• String shuffle: circuits and graphs
• Tree shuffle
• Characterization and complexity results on jumping finite automata
• scientific article; zbMATH DE number 897900 (Why is no real title available?)

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)