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

DOI10.1051/ita:2001125zbMath0994.68084OpenAlexW2151713665MaRDI QIDQ4331053

Andrzej Szepietowski, Joanna Jȩdrzejowicz

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

zbMATH Keywords

complexity of languages

Mathematics Subject Classification ID

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

Related Items (2)

Unshuffling a square is NP-hard ⋮ String shuffle: circuits and graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of iterated shuffle
• Flow languages equal recursively enumerable languages
• Shuffle languages are in P
• Very special languages and representations of recursively enumerable languages via computation histories
• Software Descriptions with Flow Expressions

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