On the expressive power of the shuffle operator matched with intersection by regular sets

DOI10.1051/ITA:2001125MaRDI QIDQ4331053zbMATH OpenOpenAlexFDO

Authors Joanna Jȩdrzejowicz, Andrzej Szepietowski

Publication date 3 June 2002

Published in RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=ITA_2001__35_4_379_0, http://www.numdam.org/item?id=ITA_2001__35_4_379_0/, https://eudml.org/doc/221957

zbMATH Keywords

complexity of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 992018
• Shuffle languages are in P
• The expressive power of the shuffle product

Cites work

• scientific article; zbMATH DE number 3936518 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1390081 (Why is no real title available?)
• Flow languages equal recursively enumerable languages
• On the complexity of iterated shuffle
• Shuffle languages are in P
• Software Descriptions with Flow Expressions
• Very special languages and representations of recursively enumerable languages via computation histories

Cited in

(8)

• Unshuffling a square is NP-hard
• scientific article; zbMATH DE number 992018 (Why is no real title available?)
• On shuffling a word with its letter-to-letter substitution
• On the interdependence between shuffle and crossing-over operations
• Extending regular expressions with iterated shuffle
• Shuffled languages -- representation and recognition
• String shuffle: circuits and graphs
• The expressive power of the shuffle product

This page was built for publication: On the expressive power of the shuffle operator matched with intersection by regular sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4331053)