Algorithmic and algebraic aspects of unshuffling permutations

DOI10.1016/J.TCS.2018.02.007MaRDI QIDQ1749534zbMATH OpenOpenAlexFDO

Authors 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

shufflepermutationcoproductpermutation avoidance

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) 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 directed perfect matchings, we prove that recognizing square permutations is {�f NP}-complete.

Recommendations

• Unshuffling permutations
• Unshuffling permutations: trivial bijections and compositions
• Publication:4946101
• scientific article; zbMATH DE number 2081004
• The shuffle algebra and its derivations
• On a conjecture concerning shuffle-compatible permutation statistics
• Algorithms and Properties on Balanced Permutations
• An algorithm computing combinatorial specifications of permutation classes
• Shuffles of permutations and the Kronecker product
• scientific article; zbMATH DE number 2145159

Cites work

• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• A note on decidability questions on presentations of word semigroups
• Coalgebras and Bialgebras in Combinatorics
• Efficient recognition of rational relations
• Hopf algebra of permutation pattern functions (extended abstract)
• Le calcul rapide des mélanges de deux mots. (Fast computing of the shuffle of two words)
• NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRAS
• On recognizing words that are squares for the shuffle product
• On the complexity of iterated shuffle
• On the computational complexity of a merge recognition problem
• On the groups \(H(\Pi,n)\). I
• Pattern matching for permutations
• Restricted permutations
• Shuffling and unshuffling
• Unshuffling a square is NP-hard
• Unshuffling permutations

Cited in

(6)

• Unshuffling permutations
• On recognizing words that are squares for the shuffle product
• The lengths for which bicrucial square-free permutations exist
• Recognizing binary shuffle squares is \textsf{NP}-hard
• Unshuffling a square is NP-hard
• An algebraic approach for the search space of permutations with repetition

Describes a project that uses

Uses Software

• OEIS

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

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