Unshuffling permutations

DOI10.1007/978-3-662-49529-2_38zbMATH Open1412.68160arXiv1601.05962OpenAlexW3038043012MaRDI QIDQ2802964FDOQ2802964

Authors: Samuele Giraudo, Stéphane Vialette 

Publication date: 3 May 2016

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

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.

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

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

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)

Cited In (7)

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

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)