Unshuffling permutations

DOI10.1007/978-3-662-49529-2_38MaRDI QIDQ2802964zbMATH OpenOpenAlexFDO

Authors Samuele Giraudo, Stéphane Vialette

Publication date 3 May 2016

Published in LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: A permutation is said to be a square if it can be obtained by shuffling two order-isomorphic patterns. The definition is intended to be the natural counterpart to the ordinary shuffle of words and languages. In this paper, we tackle the problem of recognizing square permutations from both the point of view of algebra and algorithms. On the one hand, we present some algebraic and combinatorial properties of the shuffle product of permutations. We follow an unusual line consisting in defining the shuffle of permutations by means of an unshuffling operator, known as a coproduct. This strategy allows to obtain easy proofs for algebraic and combinatorial properties of our shuffle product. We besides exhibit a bijection between square $(213,231)$-avoiding permutations and square binary words. On the other hand, by using a pattern avoidance criterion on oriented perfect matchings, we prove that recognizing square permutations is $mathbfNP$-complete.

Recommendations

• Algorithmic and algebraic aspects of unshuffling permutations
• On recognizing words that are squares for the shuffle product
• A note on square-free shuffles of words
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Pattern avoidance in permutations and their squares

Cited in

(7)

• Recognizing binary shuffle squares is \textsf{NP}-hard
• \(S\)-crucial and bicrucial permutations with respect to squares
• On square permutations
• Unshuffling permutations: trivial bijections and compositions
• Algorithmic and algebraic aspects of unshuffling permutations
• On recognizing words that are squares for the shuffle product
• The lengths for which bicrucial square-free permutations exist

This page was built for publication: Unshuffling permutations

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