S. Ahal and Y. Rabinovich, On Complexity of the Subpattern Problem, SIAM Journal on Discrete Mathematics, vol.22, issue.2, p.629649, 2008.
DOI : 10.1137/S0895480104444776

M. H. Albert, M. D. Atkinson, M. Bouvel, N. Ru²kuc, and V. Vatter, Geometric grid classes of permutations, ArXiv e-prints, 2011.

M. H. Albert, M. Lackner, M. Lackner, and V. Vatter, The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations, pp.ArXiv e-prints, 2015.

M. H. Albert, R. E. Aldred, M. D. Atkinson, and D. A. Holton, Algorithms for Pattern Involvement in Permutations, Proc. International Symposium on Algorithms and Computation (ISAAC), p.355366, 2001.
DOI : 10.1016/S0012-365X(96)83023-8

M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discrete Mathematics, vol.300, issue.1-3, p.15, 2005.
DOI : 10.1016/j.disc.2005.06.016

H. Michael, R. E. Albert, M. D. Aldred, D. A. Atkinson, and . Holton, Algorithms for pattern involvement in permutations, p.355367, 2001.

D. Aldous and P. Diaconis, Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem, Bulletin of the American Mathematical Society, vol.36, issue.04, p.413432, 1999.
DOI : 10.1090/S0273-0979-99-00796-X

M. Percy and A. , Combinatory Analysis, 1915.

H. Aoki, R. Uehara, and K. Yamazaki, Expected length of longest common subsequences of two biased random strings and its application, RIMS Kokyuroku, 2001.

R. Arratia, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, 1999.

S. Avgustinovich, S. Kitaev, and A. Valyuzhenich, Avoidance of boxed mesh patterns on permutations, Discrete Applied Mathematics, vol.161, issue.1-2, p.51, 2013.
DOI : 10.1016/j.dam.2012.08.015

URL : https://doi.org/10.1016/j.dam.2012.08.015

D. Avis and M. Newborn, On pop-stacks in series, Utilitas Mathematica, vol.19, p.129140, 1981.

M. J. Bannister, Z. Cheng, W. E. Devanny, and D. Eppstein, , pp.ArXiv e-prints, 2013.

M. J. Bannister, W. E. Devanny, and D. Eppstein, Small Superpatterns for Dominance Drawing, pp.ArXiv e-prints, 2013.

S. Bespamyatnikh and M. Segal, Enumerating longest increasing subsequences and patience sorting, Information Processing Letters, vol.76, issue.1-2, 2000.
DOI : 10.1016/S0020-0190(00)00124-1

P. Bille and I. L. Gørtz, The tree inclusion problem, ACM Transactions on Algorithms, vol.7, issue.3, p.38, 2011.
DOI : 10.1145/1978782.1978793

P. Bille and I. L. Gørtz, The tree inclusion problem, ACM Transactions on Algorithms, vol.7, issue.3, p.608124, 2006.
DOI : 10.1145/1978782.1978793

P. Bose, J. F. Buss, and A. Lubiw, Pattern matching for permutations, Information Processing Letters, vol.65, issue.5, p.277283, 1998.

M. Bouvel, D. Rossin, and S. Vialette, Longest common separable pattern between permutations, Proc. Symposium on Combinatorial Pattern Matching (CPM), p.316327, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00128750

M. Bouvel, D. Rossin, and S. Vialette, Longest Common Separable Pattern between Permutations, Symposium on Combinatorial Pattern Matching (CPM'07), p.316327, 2007.

D. Pierre, B. , and P. Crescenzi, Introduction to the theory of complexity, 1994.

M. Bruner and M. Lackner, The computational landscape of permutation patterns, ArXiv e-prints, 2013.

M. Bruner and M. Lackner, A fast algorithm for permutation pattern matching based on alternating runs, 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), p.261270, 2012.

S. Buss and M. Soltys, Unshuing a square is NP-hard, Journal of Computer and System Sciences, vol.80, issue.4, p.766776, 2014.

T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to algorithms, 2009.

M. Crochemore and E. Porat, Fast computation of a longest increasing subsequence and application, Information and Computation, vol.208, issue.9, 2010.
DOI : 10.1016/j.ic.2010.04.003

URL : https://hal.archives-ouvertes.fr/hal-00742044

S. Eilenberg and S. M. Lane, On the Groups H(??, n), I, The Annals of Mathematics, vol.58, issue.1, p.55106, 1953.
DOI : 10.2307/1969820

H. Eriksson, K. Eriksson, S. Linusson, and J. Wästlund, Dense Packing of Patterns in a Permutation, Annals of Combinatorics, vol.11, issue.3-4, p.459470, 2007.
DOI : 10.1007/s00026-007-0329-7

W. Fulton, Young tableaux : with applications to representation theory and geometry, 1997.
DOI : 10.1017/CBO9780511626241

S. Giraudo and S. Vialette, Unshuing Permutations, ArXiv e-prints, 2016.

S. Giraudo and S. Vialette, Unshuing permutations, 12th Latin American Theoretical Informatics Symposium (LATIN), p.509521, 2016.

S. Guillemot and D. Marx, Finding small patterns in permutations in linear time, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) SIAM, p.82101, 2014.
DOI : 10.1137/1.9781611973402.7

URL : http://epubs.siam.org/doi/pdf/10.1137/1.9781611973402.7

S. Guillemot and S. Vialette, Pattern Matching for 321-Avoiding Permutations, Proc. 20-th International Symposium on Algorithms and Computation, p.10641073, 2009.
DOI : 10.1007/978-3-642-10631-6_107

URL : https://hal.archives-ouvertes.fr/hal-00620322

L. Ibarra, Finding pattern matchings for permutations, Information Processing Letters, vol.61, issue.6, p.293295, 1997.
DOI : 10.1016/S0020-0190(97)00029-X

V. Jelínek and J. Kyn£l, Hardness of Permutation Pattern Matching, ArXiv e-prints, 2016.

P. Kilpeläinen and H. Manilla, Ordered and Unordered Tree Inclusion, SIAM Journal on Computing, vol.24, issue.2, p.340356, 1995.
DOI : 10.1137/S0097539791218202

S. Kitaev, Patterns in permutations and words, 2013.

D. E. Knuth, Fundamental algorithms The Art of Computer Programming, 1973.

E. Donald and . Knuth, The art of computer programming): Fundamental algorithms, 1997.

M. Kubica, T. Kulczy«ski, J. Radoszewski, W. Rytter, and T. Wale«, A linear time algorithm for consecutive permutation pattern matching, Information Processing Letters, vol.113, issue.12, p.433, 2013.
DOI : 10.1016/j.ipl.2013.03.015

L. Mach, Parameterized complexity : permutation patterns, graph arrangements , and matroid parameters, p.2015

H. Magnusson and H. Ulfarsson, Algorithms for discovering and proving theorems about permutation patterns, ArXiv e-prints, 2012.

D. Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM, vol.25, issue.2, p.322336, 1978.
DOI : 10.1145/322063.322075

A. Manseld, On the computational complexity of a merge recognition problem, Discrete Applied Mathematics, vol.5, p.119122, 1983.

A. Miller, Asymptotic bounds for permutations containing many dierent patterns, Journal of Combinatorial Theory, issue.116 1, pp.92-108, 2009.

B. E. Neou, S. Rizzi, and . Vialette, Pattern Matching for Separable Permutations, p.260272
DOI : 10.1201/b18255-15

URL : https://hal.archives-ouvertes.fr/hal-01798554

H. Prodinger and F. J. Urbanek, Innite 01-sequences without long adjacent identical blocks, Discrete Mathematics, vol.28, issue.277, p.289, 1979.

D. Henshall, N. Rampersad, J. Shallit, . Shuing, and . Unshuing, , 2011.

A. Restivo, The Shue Product: New Research Directions, Proceedings of the Ninth International Conference on Language and Automata Theory and Applications, p.7081, 2015.

R. Rizzi and S. Vialette, On recognizing words that are squares for the shue product, The 8th International Computer Science Symposium in Russia, Lecture Notes in Computer Science, vol.7913, p.235245, 2013.
DOI : 10.1007/978-3-642-38536-0_21

D. Rossin and M. Bouvel, The longest common pattern problem for two permutations, Pure Mathematics and Applications, vol.17, p.5569, 2006.
URL : https://hal.archives-ouvertes.fr/hal-00115598

C. Schensted, Longest increasing and decreasing subsequences, 1961.

J. Van-leeuwen and M. Nivat, Ecient recognition of rational relations, Information Processing Letters, vol.14, issue.1, p.3438, 1982.

Y. Vargas and . Hopf-algebra, 26th International Conference on Formal Power Series and Algebraic Combinatorics DMTCS Proceedings, p.839850, 2014.

V. Vatter, Permutation classes, Handbook of Enumerative Combinatorics, p.753818, 2015.