Algorithmic and algebraic aspects of unshuffling permutations

DOI10.1016/J.TCS.2018.02.007zbMath1390.68513arXiv1805.08255OpenAlexW2791499435MaRDI QIDQ1749534

Samuele Giraudo, Stéphane Vialette

Publication date: 17 May 2018

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

Full work available at URL: https://arxiv.org/abs/1805.08255

zbMATH Keywords

shufflecoproductpermutationpermutation avoidance

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Pattern matching for permutations
• On the complexity of iterated shuffle
• Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words)
• Efficient recognition of rational relations
• On the computational complexity of a merge recognition problem
• A note on decidability questions on presentations of word semigroups
• Unshuffling a square is NP-hard
• On the groups \(H(\Pi,n)\). I
• Unshuffling Permutations
• Coalgebras and Bialgebras in Combinatorics
• NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRAS
• On Recognizing Words That Are Squares for the Shuffle Product
• Restricted permutations

This page was built for publication: Algorithmic and algebraic aspects of unshuffling permutations