Frédérique Bassino

Sylvie Hamel

Cyril Nicaud

Adeline Pierro

Dominique Rossin

Je

Jean-Christophe Novelli

Claire David

Corinne Palescandolo

Philippe Gambette

Antoine Meyer

Xavier Goaoc

Ma

Merci à tous, Emerite

Chapter 1 Introduction

A permutation σ is said to occur in another permutation π (or π contains σ), denoted σ π, if there exists a subsequence of elements of π that has the same relative order as σ; otherwise, π is said to avoid the permutation σ. For example, a permutation contains the permutation 123 (resp. 321) if it has an increasing (resp. a decreasing) subsequence of size 3. Similarly, 213 occurs in 6152347, although 231 does not occur in 6152347. In the last decade, the study of patterns in permutations has become a very active area of research [START_REF] Kitaev | Patterns in permutations and words[END_REF] and a conference (Permutation Patterns) focuses on patterns in permutations. We consider here the so-called permutation pattern matching (noted PPM), which is also sometimes referred to as the pattern involvement problem: Given two permutations σ of size k and π of size n, the problem is to decide whether σ π (the problem is attributed to Wilf in [START_REF] Bose | Pattern matching for permutations[END_REF]). The PPM is known to be NP-hard [START_REF] Bose | Pattern matching for permutations[END_REF]; however, it is polynomial-time solvable by brute-force enumeration if σ has a bounded size. Improvements to this algorithm were presented in [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] and [START_REF] Albert | Algorithms for pattern involvement in permutations[END_REF], the latter describing a O(n 0.47k+o(k) )-time algorithm. Bruner and Lackner [START_REF] Bruner | The computational landscape of permutation patterns[END_REF] gave a xed-parameter algorithm solving the PPM problem with an exponential worst-case runtime of O(1.52 n nk). This is an improvement upon the O(k n k ) runtime required by brute-force search without imposing restrictions on σ and π, in which one has to enumerate all of the n k dierent subsequences of size k in π and test if one of them has the same relative order as σ. Guillemot and Marx [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF] showed that the PPM problem is solvable in 2 O(k 2 log k) n, and hence is xed-parameter tractable with respect to the size k of the pattern σ (standard parameterisation). However, Mach proved that the permutation involvement problem under the standard parameterisation does not have a polynomial size kernel (assuming NP ⊆ coNP/ poly [START_REF] Mach | Parameterized complexity : permutation patterns, graph arrangements, and matroid parameters[END_REF]). A few particular cases of the PPM problem have been attacked successfully. The case of increasing patterns is solvable in O(n log log k)-time [START_REF] Crochemore | Fast computation of a longest increasing subsequence and application[END_REF], improving the previous 30-year bound of O(n log k). Furthermore, the patterns 132, 213, 231 and 312 can all be handled in linear-time by stack sorting algorithms. Any pattern of size 4 can be detected in O(n log n) time [START_REF] Albert | Algorithms for pattern involvement in permutations[END_REF]. Algorithmic issues related to 321-avoiding patterns matching for permutations have been investigated in [START_REF] Guillemot | Pattern matching for 321-avoiding permutations[END_REF], [START_REF] Albert | The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations[END_REF] and more recently in [START_REF] Jelínek | Hardness of Permutation Pattern Matching[END_REF].

This thesis studies specic cases of the PPM problem. We focus especially on the cases in which the text and/or pattern are separable permutations. We expose dierent solution for both cases and propose solutions of our own. Re-lated subjects to PPM are also solved, such as the union and consensus of two permutations. Moreover, we look at the PPM when considering bivincular pattern, which we believe, is the most valuable contribution as this is the rst time that these patterns are studied. We delve deeper in the separable permutation as we also study a subclass of separable permutations, namely the wedge permutations. In particular, the case in which both the pattern and the text are wedge permutations, only the text is a wedge permutation and the pattern is a bivincular for the PPM problem are considered. We present polynomial solutions for these cases. An algorithm for the longest wedge permutation is also given.

This thesis has two main motivations. Our rst motivation is to get closer to the PPM's application, especially for bioinformatic, which focuses on sequences of genetic material such as DNA, RNA, or protein sequences. In particular for the DNA sequence, its transmission is studied. However, this transmission may result in the modication of the sequence: some parts can be added, removed or swapped. As such, it is a problem to decide whether two sequences are related. More generally, deciding whether a trait (which is a characteristic of an individual), given as a sequence, is present in a DNA sequence is a problem. Nonetheless, not all modications occur, as some are lethal to the descendant and cannot thus be observed. As such, there is a logic in a sequence and it can thus split into blocs. Moreover, we know that some blocs are conserved in order for the trait to be present. So for a trait to be present in a sequence, it must contains blocs such that they appear in the same order as the blocs of trait. The PPM is found when labelling each bloc by a number. Additionally, the blocs cannot be ordered arbitrarily. There may be some dependencies between blocs (depending on the trait), such as, some blocs cannot be in the same trait and some blocs need to be next to each other. We represent this dependencies with the avoiding classes and the bivincular patterns. Our second motivation is to grasp a better understanding over some objects. Obviously, the rst objects are separable permutations and wedge permutations, in which we explore their structures. This can be used in random generation and combinatorics. The second object is the bivincular patterns, which is tool not yet well-known. The study of bivincular patterns is the continuity of the study of permutation pattern as bivincular pattern generalise permutation pattern.

The thesis is organised as follows. The second chapter outlines the justication for this thesis. The third chapter denes the principal notions needed for the study. The fourth chapter presents the results known for the PPM problem and some variants of the problem at the time of writing. The next chapter oers results related to problems based on the PPM. Chapter ve is devoted to the study of the PPM over separable permutations, whereas chapter six focus on the wedge permutations. Finally, the conclusion proposes research leads that we consider relevant.

Chapter 2

Context of the Thesis 2.1 Non-deterministic Polynomial Problem

A computational complexity theoretician classies the problem by how hard solving it is and measures the diculty of the problem by scaling the "size of the problem" to the resources needed to solve it. Such theoreticians consider two types of resources: the number of steps needed to go from the information given in the problem to the solution and the space consumption, which is how much information is needed to nd the solution. The number of steps is tied to the time spent solving the problem, so by convention, the number of steps is refereed as the time consumption. A prime piece of information lies at the end of the theoretician's work: whether we can nd a practical method to solve the problem. All the tools and knowledge related to computational complexity theory that we need for this thesis are presented below.

The Notion of Problem

In computer science, a problem is a question or task over a class of object. An example of a problem over subsets of integers is to nd the maximal value contained in the set. A problem paired with an object of the class is an instance of a problem. A possible instance of the above problem is nding the maximal value contained in the set {3, 4, 8, 2}. The scaling is undertaken with the size of the object, with what we call size depending on the object. In the above example, the input's size would be the number of integers, so 4. A problem is said to be solvable if an algorithm can nd the solution of any instances of that problem.

Reduction: Transforming one Problem into Another

A reduction is the act of transforming any instance of a rst problem to an instance of another problem. Informally, this corresponds to representing a problem in a dierent way. The original and obtained instances must have the same solution. To understand a reduction, imagine that we want to throw a six-sided die, but do not have one. Luckily, we have six dierent cards. We can draw randomly one of the six cards to simulate a throw of a six-sided die.

The problem of throwing a die can thus be reduced to the problem of drawing a card. Reduction is used for two purposes, as described below.

Solving a Problem with a Reduction

The rst role of reduction is to solve a problem, as in the above examples. The principle is that if we have an original problem that is not yet solvable, we can use a second problem that is solvable to solve the rst one. If we know how to reduce any instances of the original problem into an instance of the second problem, then an algorithm to solve the original problem is to transform any instance of the original problem into an instance of the second problem and to solve the created instance. A simple example is a reduction of the problem of sorting a set of words in the shortlex index (which corresponds to sorting words by the number of letters and then sorting in lexical order) to the problem of sorting a set of integers; the reduction associates a word w 1 w 2 . . . w n to the number Σ 1≤n p(w i ) * s i where p(w i ) is the position of the letter w i in the alphabet, and s is the number of letters in the alphabet.

Classifying a Problem

The second purpose of reduction is to classify a problem. Indeed, if a problem can be reduced to a second one, then the second problem needs at least as many resources to be solved as the original (according to, the above strategy, and under the condition that the reduction costs less than or is proportionally the same as the cost of computing the second problem's solution). As an informal example, we can simulate a unique throw of a die by drawing in twelve dierent cards, by associating one side of a die to two dierent cards. This result in drawing in twelve dierent cards being at least as dicult as throwing a die once.

The Classes of Problems

As example above shows, we can simulate a unique throw of a die by drawing twelve dierent cards. However, we cannot simulate a drawing from twelve dierent cards with a unique throw of a die. This example shows that some problems are harder than others. This gives the intuition that we can classify problems, by what a problem can be reduced to. There is 2 dierent main classes that we are interested in.

The Class of Polynomial Problems

The class of polynomial problems is the class of problem that can be solved, and the time consumption is polynomial by the size of the input.

The Class of NP-Complete Problems.

The class of NP (non-deterministic polynomial-time) problem is the class of problem where we can check, in polynomial time, if an answer is a solution of a problem. A problem M is an NP-Hard problem if there exists an NP-Hard problem N and if N can be reduced to M. A problem is NP-Complete if it is NP and NP-Hard. Under the assumption that P = N P , the class of NP-Complete problems can be understood as the class of problems that can be solved at best in exponential time by the size of the input. Basically, when a problem is NP-complete, no algorithm can be used in practice. The following example illustrates this point. Imagine that we have a problem and an algorithm that solves that problem in 2 n , where n represents the size of the input. If the size of the input is 60, this instance will be roughly solved in 1.10 18 steps. Today's computers (a one Ghz CPU) can make 1000000000 steps per second, which means that this problem will be solved in 1.10 9 seconds, or 277777 hours, or 11574 days, or 31 years. Not anyone can aord to wait 31 years to have a question answered.

When a Problem is NP-Complete

Solutions exist whenever we need to solve an instance of an NP-Complete problem.

In practice, not every instance can appear and we use this to our advantage. An extreme case to consider is whether there is a nite number of instances; in that case, one can consider computing every instance (if temporally possible) and keeping the solutions somewhere. Another case to consider, is whether the instances have constraints; in that case, the constraints may allow to compute a solution faster than a general instance. This case can be illustrated with the problem of sorting a sequence of numbers. This problem is known to be solvable in O(n log n) time and constant space memory, where n is the size of the sequence for any sequence. However this problem is solved by the counting sort algorithm, which solves this problem in O(mn) time where m is the maximal value and n is the size of the sequence but in O(m) space. So, if we we give the constraint for the maximal element to be lower than log n, the latter algorithm is the best algorithm.

Another possibility is the class of Fixed Parameter Tractable (noted FPT) problems. The class of FPT problems is a subclass of the NP-complete problems. A problem is FPT if its input can be split into two parts and can be solved in exponential time by the size of the rst part of the input while polynomial time by the size of the second part of the input. When a problem is FPT, one can hope for a practical algorithm; indeed, if the rst part of the input is known to be always very small then even if the algorithm is exponential, the algorithm would still be runnable in human time. There exist others classes of NP-Complete problems other than the class of FPT problems. A notable hierarchy of class is the W -hierarchy (formed by the classes W [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF], W [START_REF] Albert | Geometric grid classes of permutations[END_REF], . . .). These classes are used to represent how hard it is to check whether an answer is a solution to a problem.

The Relation With This Thesis

The main problem studied in this thesis is NP-Complete. The goal of this section was to examine the intuition that using brute force to solve an instance of the problem may not be the best solution. We refer the reader to [START_REF] Pierre | Introduction to the theory of complexity[END_REF] We adopted the rst point of the above paragraph, adding constraints to the input to dene classes and nd a polynomial algorithm to solve the problem for this class.

Chapter 3

Denitions

This chapter provides general denitions needed for this thesis.

Permutations

Denitions for Permutation

Denition 1. A permutation of size n is a linear order of a ordered set of size n.

Most of the time, the set used in Denition 1 is {1, 2, . . . , n}, the set of the n rst integers. We write a permutation as a word, the linear order of the permutation is encoded in that word: pick a letter in that word, any letter on its left is smaller than the picked letter and any letter on its right is larger than the picked letter. To work with permutation, we use notation borrowed from words: Given an element e, we refer by its index (usually represented by the letters i, j, ) its position in the word. Moreover, given an i, π[i] denotes the element with index i. For example, given that π = 52143, π [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF] = 3 and the element 5 has 1 for its index.

The Representation of a Permutation.

Associating a permutation with a gure that we call a plot is helpful for understanding some algorithms. A plot represents a permutation by associating every element to a point of coordinate (i, π[i]). The plot reveals the linear orders: the set's linear order is the elements read from bottom to top and the permutation's linear order is the elements read from left to right. See Figure 3.1 for the plot of the permutation π = 52143.

Comparing the Elements of a Permutation Value and Position of an Element

We need to consider both the set's linear order and permutation's linear order. When we talk about an element, we refer to its relative position in the set's linear order as its value, and its relative position in the permutation's linear order as its position. We usually use i, j and to represent an element's position and

Comparing Two Elements by Value

When an element e 1 is smaller (resp. larger) than an element e 2 by value (in the set's linear order), we say that e 1 is below (resp. above) e 2 . Moreover, the element with the largest value is called the topmost element and the element with the smallest value is referred to as the bottommost element. For example, in the permutation π = 52143, 2 is below 4, the top most element is 5 and the bottommost element is 1. We can nd the natural linear order of the set by reading the element from bottom to top, which explains why we say that an element is above or below another element.

Comparing Two Elements by their Positions

When an element e 1 is smaller (resp. larger) than an element e 2 by position (in the permutation's linear order), we say that e 1 is on the left (resp. right) of e 2 . Besides, the element with the largest position is called the rightmost element and the element with the smallest position is called the leftmost element. For example, in the permutation π = 52143, 5 is on the left of 2, the leftmost element is 5 and the rightmost element is 3. We can nd the linear order given by the permutation by reading the element from left to right, which explains why we say that an element is on the left or on the right of another element.

A Subsequence of a Permutation

It is useful to consider only part of a permutation. To do so, we are allowed to remove elements of that permutation. For instance, in the permutation 52143, one may want to consider only the elements with a value above 1; intuitively, the subsequence permutation is 5243. Formally speaking, a subsequence of a permutation π is any permutation that can be obtained from π by deleting some elements without changing the linear order of the remaining elements. Note that when subsequences of a permutation are being discussed, "of a permutation" is omitted.

Omitting Elements by Values with Bounds

When we want to delete elements by their values, we write π{inf : sup} to indicate that we are considering only the elements with values between inf and sup. We write π{inf :} if we are considering elements with values above to inf (this is equivalent to writing π{inf : n} if π has n elements) and π{: sup} if we are considering elements below sup (this is equivalent to writing π{1 : sup}). For example, in the permutation π = 52143, π{: 3} = 213, π{2 :} = 543 and π{2 : 4} = 243. The disregarding of elements by their values can be understood by drawing two horizontal lines and omitting the elements between the two lines. See

Rectangle of a Permutation

Generally speaking, whenever we consider a subsequence of elements of a permutation by selecting the elements by bounding them by value and/or by position, the subsequence is called a rectangle. The name comes from the plot of a permutation as, a simple way to see all the elements of a rectangle is to draw a rectangle with each edge dened with the bounds; every element that is in the rectangle is part of the subsequence. To stay constant with the general denition of a rectangle, we describe a rectangle as two points (A, B), where A is the bottom left corner and B is the top right corner. For instance, the rectangle ((2, 2), (4, 4)) of the permutation 52143 is 24. See Figure 3 We will be led to comparing two rectangles in this thesis, however not all pairs of rectangles are comparable: two rectangles are comparable if and only if they are not empty, the rst rectangle's top right corner is to the left of and below the bottom left corner of the second rectangle, or its bottom right corner is on the left of and above the top left corner of the second rectangle. In the plot, two rectangles are comparable if and only if there do not exist any horizontal or vertical splices that contain both rectangles. Based on those constraints, when two rectangles are compared, one is always completely above/below the other and one is always completely on the right/left of the other.

Remark 2. This thesis does not use the notation to bound the elements by value. Only the notation to bound the elements by position and the notation of a rectangle are used.

Elements of a Subsequence

In relation to subsequences of a permutation and comparing elements, the following denitions of element are needed for this thesis. Denition 3. We call the left-to-right maximum (noted LRMax) of a permutation π at index i, the maximal element in the permutation π[: i].

Denition 4. We call the left-to-right minimum (noted LRMin) of a permutation π at index i, the minimal element in the permutation π[: i].

Denition 5. We call the right-to-left maximum (noted RLMax) of a permutation π at index i, the maximal element in the permutation π[i :].

Operations on Permutation

Transforming a Permutation

The following operations are not used directly in this thesis, but they allow to generalise result proved for one class of permutation to others classes. These operations create bijection between classes of permutations; as such, an algorithm that treats only one class of permutations can be used if we know how to transform a permutation of another class into a permutation of this class.

The Reverse of a Permutation Denition 7. The reverse of a permutation π, is the permutation τ , where the set's linear order is the same as π but the permutation's linear order is reversed.

Reversing a permutation corresponds to reading the permutation from right to left. In a plot, this corresponds to a reection on the y-axis. For example, the reverse of the permutation 391867452 is 254768193. See Figure 3.5.

The Complement of a Permutation Denition 8. The complement of a permutation π, is the permutation τ where the linear order of the permutation is the same as π but the linear order of the set is reversed.

Mapping

Denition 9. Given a permutation σ of size k and a permutation π of size n, a mapping φ from σ to π is an injective function dene as φ : {1, 2, . . . , k} → {1, 2, . . . , n}.

A mapping from a permutation σ to a permutation π is an usual mapping: Each element of σ is associated with an element of π, and no element of π has two dierent inverse images. We map the elements with their positions in σ to the position of elements in π, as positions reveal an element's value. See Figure 3.7 for an example of mapping.

Remark 10. The mapped elements form a permutation: The elements have their natural linear order and reading the mapping from left to right yields a total linear order. Denition 11. Given a permutation σ of size k and a permutation π of size n, an increasing mapping is a mapping φ from σ to π such that if i < j then φ(i) < φ(j).

For our purposes, we only need to consider increasing mapping. In other words, if two elements are increasing by position then the positions of their images by the mapping are also increasing. As we map elements by their positions, we only require the mapping to be increasing. In the Figure 3.7 this corresponds to not having crossing lines. See Figure 3.8 for an example of an increasing mapping.

We write increasing mapping as a word, where the i th letter is the image of i by the mapping in π :

φ = π[φ(1)]π[φ(2)] . . . π[φ(k)].
We do not loose any information by doing so, as the inverse of a letter is found in the position of that letter. For example, the mapping of Figure3.8 is written as 91645. An increasing mapping can be accomplished in two ways: If the permutation is written as a word, making an increasing mapping consists of selecting as many elements in 12 Figure 3.9 Two ways to represent the mapping 916745 in 391867452: The rst one is to select the points and the second is to bold the selected elements in the permutation.

π as there are elements in σ. In other words, we want a subsequence of π of the same size as σ. For this reason, we represent a mapping by a subsequence. If we have the plot of π, an increasing mapping consists of selecting as many points in the plot of π as there are elements in σ. See Figure 3.9 for an example.

Reduction of a Permutation

The set of a permutation is not always the set {1, 2, . . . , n}. For example, the permutation given by the images of a mapping and the permutation given by a rectangle are permutations over a set which is not the rst integers. We can also imagine a permutation over any set, as long as we have a linear order over this set. We called those permutations "non-canonical".

The rst case of non-canonical permutations described above turns out to be a problem: When reading the permutation from left to right, we cannot guess the relative order (in the linear order by value) of an element until we read all of the elements. For example, in the permutation 91645, we cannot know that 6 is the second largest element from having read 916.

It should also be noted that we only need the linear order between the value of the elements. So the actual values of the elements do not matter as long as this linear order is preserved.

It is in our best interest to work with a canonical permutation, that is a permutation of size n with domain {1, 2, . . . , n}. As we do many operations on a permutation, it is better to spend some time computing a permutation that is easy to handle and understand rather than using a "hard" permutation and spending time to make operations on it. We call the operation that goes from a non-canonical permutation to an canonical permutation a reduction. Denition 12. Given a permutation π on set {e 1 , e 2 , . . . , e n } such that e 1 < e 2 < . . . < e n the reduction of π, noted as reduction(π), is the permutation in which we replace every element e i by i.

For example, 91645 has for natural linear order 1 < y 4 < y 5 < y 6 < y 9 so In a plot of a permutation this corresponds to removing every empty line of the gure. See Figure 3.10 for the reduction of 91645.

Direct Sums and Skew Sums

Denition 13. Given a permutation π 1 of size n 1 and a permutation π 2 of size n 2 , the direct sum of π 1 and π 2 is dened by:

π 1 ⊕π 2 = reduction(π 1 [1]π 1 [2] . . . π 1 [n 1 ](π 2 [1]+n 1 )(π 2 [2]+n 1 ) . . . (π 2 [n 2 ]+n 1 )).
The direct sum of two permutations is found by taking the left permutation's elements and adding the right permutation's elements such that the latter are to the right of and above the former. In other words, we take the elements of the left permutation and then add the elements of the right permutation shifted by the size of the left permutation. For example, 312 ⊕ 3214 = 321

(3 + 3)(2 + 3)(1 + 3)(4 + 3) = 3126547.
From the plots of the permutations, this corresponds to taking the points of the right permutation and putting them to the right and above the left permutation. See Figure 3.11 for the direct sum of 312 and 3214. Denition 14. Given a permutation π 1 of size n 1 and a permutation π 2 of size n 2 , the skew sum of π 1 and π 2 is dened by:

π 1 π 2 = (π 1 [1] + n 2 )(π 1 [2] + n 2 ) . . . (π 1 [n 1 ] + n 2 )π 2 [1]π 2 [2] . . . π 2 [n 2 ].
The skew sum of two permutations is formed by taking the right permutation's elements and adding the left permutation's elements such that latter are to the left of and above the former. In other words, take the elements of the right permutation and then add on the left the elements of the left permutation shifted by the size of the right permutation. For example, 312 3214 = (3 + 4)(1 + 4)(2 + 4)3214 = 7563214.

From the plots of the permutations, this corresponds to taking the points of the left permutation and putting them to the left and above the right permutation. See Figure 3.12 for the skew sum of 312 and 3214.

Order isomorphism

Two denitions of order isomorphism are presented rst, as they are needed to the denition of an occurrence. Intuitively, two permutations are order isomorphic if their linear orders are equivalent. As the natural linear order of the elements remains unchanged, this corresponds to asking for the second linear orders to be equivalent. Denition 15. Given two permutations σ and π, σ and π are order isomorphic if for all i, j, i = j,

1 ≤ i, j ≤ n, σ[i] < σ[j] if and only if π[i] < π[j].
From the plot of two permutations, one can guess if those two permutations are order isomorphic if and only if the points of the elements of the rst permutation are in the same disposition as the points of the elements of the second permutation without regard to the distance between the points. Denition 16. Given two permutations σ and π, σ and π are order isomorphic if reduction(σ) = reduction(π).

An Occurrence

The notion of an occurrence is central for the PPM problem as it is needed to dene the problem. Denition 17. An occurrence of σ in π is a subsequence s of π such that reduction(s) = reduction(σ).

If π contains an occurrence of σ, then we say that σ occurs in π, which is denoted usually as σ ≺ π; otherwise, we say that π avoids σ. For example, 98752 and 98743 are occurrences of 54321 in 391867452, so 54321 occurs in 391867452, however, 391867452 avoids 1234, as there is no increasing subsequence of size 4. See Figure 3.13 for the plot of the example.

Set of Pattern Avoidance

Denition

The notion of avoidance allows us to dene a class of permutations C : Given a set S of permutations, the class C corresponds to all permutations that do not contain any permutation in S. This class is denoted by Av(S) or S-avoiding; only the latter is used in this thesis. For the rst notation, the convention is to remove the brackets of the set. For the second notation, when the set S contains a unique permutation, we do not put parentheses.

Remark 18. This thesis only considers cases in which S is nite.

The Utilities of Classes of Permutation

The usefulness of permutations classes seems to be limited. It appears that some sets of permutations dened by their structures can be seen as sets of permutations by avoidance. This has generate interest in the eld of combinatorics, especially in enumerating a certain classes and nding a transformations of a permutation into other objects. For example, the 321-avoiding set is known to be a set of permutations that can be partitioned into two increasing subsequences.

Comparing Avoiding Sets

Some classes of permutations are more impactful for our purposes than some others. Indeed, knowing that a problem is NP-complete when considering permutations of a given class and that this class is included in another one implies that the problem is also NP-complete when considering permutations of the second class. For this purpose we need to be able to compare avoiding sets of permutations. Comparing avoiding sets can be easy: Avoiding classication forms a downset. The set of all avoiding sets is partially ordered for the inclusion. Based on what is more important, one can decide whether two sets are comparable and in this case which one is included in the other. To decide whether S 1 -avoiding is included in S 2 -avoiding, one has to decide whether every permutation of S 1 occurs in at least one permutation in S 2 . Indeed, if a permutation π 1 avoids a permutation π 2 , and π 2 occurs in π 3 , then π 1 avoids π 3 . This is because any occurrence of π 3 would contain an occurrence of π 2 , which implies that π 1 would contain an occurrence of π 2 . The downside is that one has to decide whether a permutation occurs in another permutation, which is our main problem. This approach only allows us to compare a few sets, but it is the most direct option and is sucient for our purposes.

Another possible approach is to use the structure of the two sets. For example, the set of 213-avoiding permutations is the set of permutations that are sortable by a unique stack (See [START_REF] Knuth | Fundamental algorithms[END_REF]) and the set of (2413, 3142)-avoiding permutations is the set of permutations that are sortable by an arbitrary number of stack (See [START_REF] Avis | On pop-stacks in series[END_REF]). By denition, the set of 213-avoiding permutations is included in the set of (2413, 3142)-avoiding permutations.

The Permutation Pattern Matching Problem

This section presents the main problems studied in this thesis.

The Permutation Pattern Matching Problem

We dene the PPM problem as the following decision problem: Problem 19. Given a permutation σ of size k and a permutation π of size n, k ≤ n, the PPM problem asks whether σ occurs in π.

By analogy to pattern matching for words, we call σ the pattern and π the text.

The Permutation Bivincular Pattern Matching Problem

A more general problem than the PPM problem adds constraints to the occurrence. In this thesis, we study a generalisation known as permutation bivincular pattern (noted BVP ) matching.

A BVP σ is a pattern permutation where we add constraints on the occurrence. As such a BVP σ of size k can be visualized as a "regular" permutation of size k and a set of constraints. With this visualization in mind, given a BVP σ, we let σ denote the "regular" permutation. Intuitively, for a sequence to be an occurrence of σ, it must be an occurrence for σ and respect the given constraints. Denition 20. An occurrence of σ in π is a subsequence s of π such that reduction(s) = reduction(σ) and the constraints of σ are respected.

We dierentiate two types of constraints. The rst type is constraint on the values of an occurrence. We can ask an element to be consecutive to another one, to be the bottommost element or the topmost element.

Example 21. Given the pattern 213 with the condition that the elements corresponding to 2 and 3 are consecutive, 729 is not an occurrence because 7 and 9 are not consecutive but 728 is an occurrence. Example 22. Given the pattern 213 with the condition that the element corresponding to 1 is the bottommost element, 729 is not an occurrence because 2 is not the bottommost element but 718 is an occurrence.

It should be noted that some constraints are not "compatible" with some patterns, in the sense that no sequence can be an occurrence for this BVP . For example, given the pattern 213 with the condition that the element 1 is the topmost element will never hold an occurrence because if the element representing 1 is the topmost element, no element can represent the 2 or 3.

The second type of constraint is on the position (in the text) of the element of an occurrence. We can ask an element to be next to another one in the text, to be the leftmost element or the rightmost element.

Example 23. Given the pattern 213 with the condition that the elements corresponding to 2 and 1 are next to each other in the text and given the text 43251, 425 is not an occurrence because 4 and 2 are not next to each other (in the text) but 435 is an occurrence.

Example 24. Given the pattern 213 with the condition that the element corresponding to 2 is the leftmost element and in the text and given the text 43251, 325 is not an occurrence because 3 is not the leftmost element in the test but 425 is an occurrence.

The same remark about the "compatibility" of a pattern and constraints also holds with the constraints on position.

We give here the notation of BVP , this notation is useful because we can create a BVP from a "regular" pattern by adding constraints such that the constraints and the pattern are always compatible. We denote a BVP σ of size k in a two-line notation: the top row is 12 . . . k and the bottom row is a permutation σ 1 σ 2 . . . σ k . We have the following conditions for the top and bottom rows of σ (Denition 1.4.1 in [START_REF] Kitaev | Patterns in permutations and words[END_REF]):

• If the bottom line of σ contains σ i σ i+1 . . . σ j then the elements corre- sponding to σ i σ i+1 . . . σ j in an occurrence of σ in π must be adjacent, whereas there is no adjacency condition for non-underlined consecutive elements. Moreover if the bottom row of σ begins with σ 1 then any occurrence of σ in a permutation π must begin with the leftmost element of π, and if the bottom row of σ ends with σ k then any occurrence of σ in a permutation π must end with the rightmost element of π.

• If the top line of σ contains i i + 1 . . . j then the elements corresponding to i, i + 1, . . . , j in an occurrence of σ in π must be adjacent in values, whereas there is no value adjacency restriction for non-overlined elements. Moreover, if the top row of σ begins with 1 then any occurrence of σ in a permutation π must contain the smallest element of π, and if top row of σ ends with k then any occurrence of σ in a permutation π must contain the largest element of π.

For example, let σ = 123 213 . If π i π j π is an occurrence of σ in π ∈ S n , then π i π j π = (x + 1)x(x + 2) for some 1 ≤ x ≤ n -2, i = 1 and = n. For example 316524 contains one occurrence of σ (the subsequence 324), whereas 42351 contains an occurrence of pattern σ but not the BVP σ.

We represent BVP (as well as occurrences of BVP in permutations) by plots. Such plots consist of sets of points at coordinates (i, σ[i]) drawn in the plane together with forbidden regions that represent adjacency constraints. A vertical forbidden region between two points denotes the fact that the occurrences of these two points must be consecutive in positions. It can also represents the condition on the leftmost and rightmost element, in which case we draw a forbidden area between the leftmost element and the "left border" of the plot and the rightmost element and the "right border" of the plot, respectively. In a similar approach, a horizontal forbidden region between two points denotes the fact that the occurrences of these two points must be consecutive in values. It can also represents the condition on the bottommost and topmost element, in which case we draw a forbidden area between the bottommost element and the "bottom border" of the plot and the topmost element and the "top border" of the plot, respectively. Given a permutation π and a BVP σ, the rationale for introducing these augmented plots stems from the fact that π contains an occurrence of a BVP σ if there exists a set of points in the plot of π that is order-isomorphic to σ and if the forbidden areas does not contain any points (see Figure 3 (c) An occurrence of σ in 3216745 but not σ because the points [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF][START_REF] Albert | The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations[END_REF] and [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF][START_REF] Aldous | Longest increasing subsequences: From patience sorting to the baik-deift-johansson theorem[END_REF] The rst result for the PPM problem concerns the enumeration of sequences of integers that can be partitioned into two decreasing subsequences, which are the 123-avoiding permutations.s This result can be found in [START_REF] Percy | Combinatory Analysis[END_REF], which was written in 1915 by MacMahon. The problem of nding the longest increasing (or decreasing) subsequence, which can be used to determine whether an increasing permutation 12 . . . n occurs in a permutation, was rst studied in 1961 in [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF] in a Schensted's article.

The seed of PPM is found in the notion of avoidance presented in [START_REF] Knuth | Fundamental algorithms[END_REF], where Knuth show that stack-sortable permutations can be dened as permutations that avoid 213. This new way of characterisation provided a powerful tool to the combinatorics eld. The combinatorics used the notion of avoidance to enumerate permutations and create new generating functions. This also led to the creation of new bijections between permutations of a certain class and other objects, some of which, are useful in the current study. In this thesis we are only interested in the algorithmic part of the PPM problem. A more combinatorial overview of PPM can be found in [START_REF] Vatter | Permutation classes, Handbook of Enumerative Combinatorics[END_REF] written by Vatter whereas, a more general overview can be obtained from Kitaev's book [START_REF] Kitaev | Patterns in permutations and words[END_REF].

The rst "ocial" appearance of PPM occurred at the 1992 SIAM Discrete Mathematics meeting, where Wilf asked the community whether there exists an algorithm that solve the PPM problem in a non-exponential time. Bosen, Buss and Lubiw presented an answer in 1993 in [START_REF] Bose | Pattern matching for permutations[END_REF], where they provided proof that the problem is NP-complete by reducing the boolean satisability problem to PPM. However, the problem is solvable by a brute force algorithm in polynomial time if the size of the pattern is xed. This algorithm was studied by Albert et al. in [START_REF] Albert | Algorithms for pattern involvement in permutations[END_REF], in which they provide a O(n k ) running time algorithm where n is the size of the text and k is the size of the pattern. The best result up to this date is attributed to Ahal and Rabinovich in [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] where they give an algorithm running in O(n 0.47k+o(k) ).

To solve the PPM problem, the algorithm using brute force checks all subsequences of size k in π, which results in a O( n k k)-time algorithm. This is because there are n k dierent subsequences. Moreover, we can check in linear time in k whether a subsequence is an occurrence of σ. This algorithm was improved by Bruner and Lackner in [START_REF] Bruner | A fast algorithm for permutation pattern matching based on alternating runs[END_REF], which present an algorithm running in O(1.52 n nk). One of the more important results is one found in [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF] by Marx and Guillemot, who show that PPM is FPT by the size of σ by giving an n.2 O(k 2 log k) -time algorithm. In the same veins as the last result P P M is FPT by the number of alternating runs in π (see [START_REF] Bruner | A fast algorithm for permutation pattern matching based on alternating runs[END_REF]), especially an algorithm running in O(1.79 run(π) nk)-time exists.

All of the results at the time of writing are as follows:

• PPM is FPT by the size of σ, especially one can decide whether σ occurs in π running in n.2 O(k 2 log k) (See [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]).

• PPM is FPT by the number of runs in π, especially one can decide whether σ occurs in π in O(1.79 run(π) .n.k) (See [START_REF] Bruner | A fast algorithm for permutation pattern matching based on alternating runs[END_REF]).

• One can decide whether σ occurs in π in O(n 0.47k+o(k) ) time for σ with a size smaller than k (See [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF]).

• One can decide whether σ occurs in π in O(1.52 n nk) time (See [START_REF] Bruner | A fast algorithm for permutation pattern matching based on alternating runs[END_REF]).

Adding Constraints to the Permutation Pattern Matching Problem

The general case of the PPM problem is NP-complete, but all hope is not lost. Some special cases can be solved polynomially. A strategy is to limit the possible inputs. Because in the PPM problem, the only inputs are the permutation π and σ, we dierentiate 3 class of constraints: if we constraint σ, if we constraint π and σ or if we constraint π. The restrictions usually consist of permutations that belong to certain classes or in a restriction on the size of the permutations. Another strategy consists of adding restrictions to an occurrences of σ; whereas these restrictions are added by considering a more general denition of a permutation pattern as a BVP or mesh pattern, we prefer to interpret them as a restriction on the output occurrence and not as a generalisation.

The Permutation Pattern Matching Problem with Specic Classes of Permutations

Separable Permutations

One of the most prominent classes of permutations studied in permutation is the class of (2413, 3142)-avoiding permutations, which are also called separable permutations. The rst paper on PPM [START_REF] Bose | Pattern matching for permutations[END_REF], which proved that the problem is NP-complete, presented a positive result for the special case in which σ is a separable permutation. The authors presented an O(kn 6 ) time algorithm by exploiting the tree structure of a separable permutation. Ibarra latter improved this algorithm in [START_REF] Ibarra | Finding pattern matchings for permutations[END_REF] to a O(kn 4 )-time and O(kn 3 )-size algorithm. In this thesis we improve this algorithm to O(n 3 log k)-space algorithm by a simple observation. Due to the tree structure of separable permutations, the PPM problem on separable permutations can be reduced to a tree inclusion problem. Many results exist for the tree inclusion problem and special cases like a tree with few leaves or tree with small depth are studied. The best algorithm is by Bille and Gørtz [START_REF] Bille | The tree inclusion problem: In linear space and faster[END_REF] who gave a O(n T ) space and

O   min    l T n T l T l T log log n T + n T n T n T log n T + n T log n T     
time algorithm, where T denotes the tree of π, T denotes the tree of σ n T (resp. n T ) denotes the number of nodes of T (resp. T ) and l T (resp. l T ) denotes the number of leaves of T (resp. T ). Whereas these algorithms are specialised for trees and somehow dicult to implement, we oer, in this thesis (in Chapter 6), a simpler approach to the PPM problem when σ and π are separable. It should be noted that this algorithm can be used to solve the PPM problem whenever the pattern avoids a pattern of size 3, except for the pattern 321 and 123. Indeed, all other patterns of size 3 are a sub-class of separable permutations.

Increasing Permutations

Another class of PPM problems was solved early, even before it ocially existed.

The increasing permutations can be characterised as the 21-avoiding permutations and for a given size k there is a unique (canonised) increasing permutation, namely the permutation 12 . . . k. As noted previously, the problem of nding the longest increasing subsequence can be used to test whether the permutation σ = 12 . . . k occurs in π: compute the size of the longest increasing subsequence in π, obviously if this size is equal to or larger than k then σ occurs in π. See [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] for the best algorithm to date for computing the longest increasing subsequence in a permutation.

321-Avoiding Permutations

The rst result related to the 321-avoiding permutation (or by symmetry the 123-avoiding permutations) is provided by Guillemot and Vialette in [START_REF] Guillemot | Pattern matching for 321-avoiding permutations[END_REF] where they give an algorithm running in O(kn 4 √ k+12 ) time for computing this problem. It is worth mentioning that the authors show that, the P P M problem with 321avoiding coloured permutations is NP-complete, in the coloured version of PPM problem, each element is associated with a colour. The problem seeks to nd an occurrence such that the i th element of the occurrence and σ have the same colour. Another positive result is recorded in the same paper: An algorithm that solves the PPM problem in O(k 2 n 6 ) time when both σ and π are 321-avoiding. This result was improved in 2015 by Albert et al. in [START_REF] Albert | The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations[END_REF] which oers an O(nm)time algorithm. The argument presented is that the set of increasing matchings that match an element of the rst (resp. second) increasing subsequence of σ to an element of the rst (resp. second) increasing subsequence of π forms a lattice. Then they use two properties of a lattice: The set is partially ordered and a unique minimal and maximal element exists. To nd an occurrence, the algorithm creates an increasing sequence of matching, starting from the minimal matching. The algorithm also assures that we choose a good matching, such that, if we are at the maximal matching and we did not nd an occurrence then no occurrence exists. Finally, Jelínek and Kyn£l in [START_REF] Jelínek | Hardness of Permutation Pattern Matching[END_REF] prove that PPM problem is NP-complete when the pattern avoids 321 and when the text avoids 4321. They also attain a positive result by showing that any PPM problem can be solved in polynomial time if the pattern is in the proper subclass of 321-avoiding permutation.

Skew-Merged Permutations

In [START_REF] Albert | The Complexity of Pattern Matching for 321-Avoiding and Skew-Merged Permutations[END_REF], Albert et al. also present an algorithm to decide whether σ occurs in π when both σ and π are Skew-merged permutations. Skew-merged permutations are the (3412, 2143)-avoiding permutations. These permutations can be understood as the permutations that can be partitioned into one increasing subsequence and one decreasing subsequence. Jelínek and Kyn£l in [START_REF] Jelínek | Hardness of Permutation Pattern Matching[END_REF] also provide a positive result over a proper subclass of skew-merged permutations, especially the (3412, 2143, 3142)-avoiding permutations. They prove that the PPM problem can be solved polynomially when the pattern is in a proper subclass of this class. It should be noted that this is the rst positive PPM result for a class that is not a subclass of separable permutations.

The Case of Fixed Permutations

Finally, whenever a pattern's size is xed, we can decide the PPM problem polynomially. We can improve this result even further for all permutations with four elements. Indeed, we obtain an O(n 1.88 )-time algorithm by applying the general algorithm. Albert et al. in [START_REF] Albert | Algorithms for pattern involvement in permutations[END_REF] provide an algorithm to solve this problem in O(n log n) time. They improve this even further for the special cases of 4312, which can be solved in linear time.

Wedge Permutations

In this thesis (in Chapter 7) we focus on wedge permutations, that are the permutations that can be split into a increasing and a decreasing subsequence such that the elements of the decreasing sequence are above the elements of the increasing sequence. We study cases in which σ is a wedge permutation and σ and π are wedge permutations. We show that when only σ is a wedge permutation, we can decide whether a permutation σ of size k occurs in a permutation π of size n in O(max(kn 2 , n 2 log log n))-time and O(n 3 )-space. We can also determine whether σ occurs in π in linear time when σ and π are wedge permutations.

Generalisation of Patterns

Complexity with Mesh or Bivincular Patterns

The PPM problem when considering permutation as pattern are a special case of the PPM problem when considering BVP . This can be generalized even more by considering mesh pattern. Mesh pattern generalises Bivincular pattern, whereas in bivincular pattern the forbidden areas are a entire columns or line of the plot, forbidden areas in mesh pattern correspond to one square of the plot. For this reason, the PPM with BVP and mesh patterns is NP-complete. It should be noted that the problem is not FPT but is W [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF]-hard (See [START_REF] Bruner | The computational landscape of permutation patterns[END_REF] section 5 for the proof). In other words, we cannot hope for FPT algorithms.

Consecutive Pattern

Some positive results come with stronger constraints on the pattern. Consider the consecutive pattern, which is a special case of BVP where all the elements are underlined. In other words, we are looking for sequence (that is, a subsequence in which all elements are contiguous) in π that is isomorphic to σ. This problem can be solved in linear time, as shown by Kubica et.al. in [40].

Boxed Mesh Pattern

Another strong constraint is when we want to decide whether an occurrence exists and is contained in a rectangle and the inside of the rectangle contains only the occurrence's elements (see Figure 4.1 for an example). These patterns are the so-called boxed mesh patterns and were examined in [START_REF] Avgustinovich | Avoidance of boxed mesh patterns on permutations[END_REF] by Avgustinovich, Kitaev and Valyuzhenich.

The problem of detecting a boxed mesh permutation was successfully studied and an algorithm running in O(n 3 )-time is shown in [START_REF] Bruner | The computational landscape of permutation patterns[END_REF].

State of the Art

This section summarize the results of the PPM problem when considering certain classes for the text and/or the pattern in the tables 4.2, 4.3 and 4.4 and of the PPM problem when considering dierent type of pattern are summarize in the table 4.5.

Point of View of this Thesis

This thesis adopted the usual strategy of adding constraints to the input and examine what happens when constraints are added to the occurrences, especially when BVP are considered. This proved to be successful, as we found polynomial algorithms for some classes; the downside was an increasing time and space consumption compared to their counterpart with permutation pattern. We will show, in what follows, that • One can decide in O(kn 4 ) time and O(kn 3 ) space whether a wedge BVP occurs in π, see Section 6.6.

• One can decide in O(kn 6 ) time whether a separable BVP occurs in π, see Section 7.4.

Condition both on σ and π

Complexity 1

Reference

Skew-merged permutations

O(nk)-time [3] Separable Permutations O(n T )-space [16] O   min    l T n T l T l T log log n T + n T n T n T log n T + n T log n T      -time 2 321-avoiding O(nk)-time [33]
Wedge permutations Linear algorithm Section 7.2 two increasing subsequences and one decreasing subsequence Chapter 5

Related problems

As in the pattern matching for words, some other problems naturally arise in relation to PPM problem. This chapter presents a non-exhaustive list of related problems.

Longest Subsequence

The longest subsequence (noted LS) problem seeks to nd the LS in a permutation belonging to a given set. The LS problem is a special case of the longest common subsequence (noted LCS) problem, which is explained in this thesis. The LS problem has mainly been studied to solve the LCS. Problem 26. Given a class of permutations S, a permutation π and an integer m, the LS problem asks whether there exists an occurrence of a permutation σ in π of size m such that σ ∈ S.

Longest Increasing Subsequence

A similar problem exists in a sequence of integers, namely the longest increasing subsequence (noted LIS) problem. Equivalently the longest decreasing subsequence (noted LDS) problem exists. The LIS problem seeks to nd in a sequence of integers the LIS. There exists many methods to compute a LIS of a sequence, to cite just a few:

• A method use the representation of a sequence of integers called Young tableau (See [START_REF] Fulton | Young tableaux : with applications to representation theory and geometry[END_REF]). In a Young tableau, a sequence is represented in a two-dimensional array, the size of the LIS is the size of the rst row (See [START_REF] Schensted | Longest increasing and decreasing subsequences[END_REF]). It should be noted that the size of the LDS is the size of the rst column.

• An algorithm use tractable strategy: For each sux of the sequence the size of LIS is computed using the following relation: A LIS of a sux corresponds to a LIS of the current sux without its rst letter concatenated to the rst letter (if possible). This algorithm run in O(n 2 ) where n is the size of the sequence.

• The best algorithm runs in O(n log n). Its principle uses patience sorting, the idea being to construct a sequence of decreasing subsequences. To do so one has to read the sequence of integers from left to right. For each number read, puts it at the end of the latest created decreasing subsequence if the subsequence is still decreasing; otherwise create a new subsequence. Once the sequence of decreasing subsequences is created, one can nd an LIS by picking one element of each decreasing subsequence.

To this end, each integer must know which element is on its left (in the original sequence), below it and on the decreasing previous subsequence (See [START_REF] Aldous | Longest increasing subsequences: From patience sorting to the baik-deift-johansson theorem[END_REF]).

Remark 27. One can easily adapt these algorithms to nd the LDS.

In terms of permutations, the LIS can be understood as the longest 21avoiding subsequence. Moreover, the (canonised) permutations have one advantage over a sequence of integers: We know every element and are sure that each one appears only once. Bespamyatnikh and Segal use this knowledge in [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF], where they provide an algorithm to compute the LIS of the longest 21-avoiding subsequence in O(n log log n), where n is the size of the permutation. Moreover, in addition to having LIS, we have the LIS for each contiguous subpermutation.

Longest Alternating Subsequence

The class of permutations is also thoroughly studied in relation to the LAS. An alternating permutation is a permutation that features elements in an alternating order: Every contiguous element is of a dierent order than the previous and next pairs (if any). A (folkloric) simple algorithm is to construct two alternating subsequences by adding the rst element of the permutation and every element that is a peak (an element π

[i] such that π[i -1] < π[i] > π[i + 1]) or a valley (an element π[i] such that π[i -1] > π[i] < π[i + 1]
) in an alternating manner, starting with peak. The second alternating subsequence follows the same scheme: The rst element of the permutation and every elements that is a peak or a valley is added in an alternating manner, starting with a valley. The longest alternating subsequence is the LS between the two subsequences created.

Remark 28. Alternating permutations are sometimes called zigzag or up/down permutations.

State of the Art

The results about longest subsequence are summarize in the table 5.1

Longest Common Subsequence

The LCS problem is the general case of LS. Instead of looking for the LS in one permutation, we look for the LS that occurs in each permutation of a set of permutations. The LCS problem is studied over words and one result is useful to us. As such, we start by introducing the problem of LCS for words, where a word is a sequence on a nite set. This problem is sometimes referred to as the consensus problem.

Longest Common Subsequence for Words

Problem 29. Given a set S of words, the LCS problem seeks to nd the LS common to all words in S.

The LCS is known to be NP-complete (See [START_REF] Maier | The complexity of some problems on subsequences and supersequences[END_REF]) when the size of the set is not bounded, even when the words are binary words. A polynomial time algorithm exists when the size of the set is xed, running in O(n k ) where k is the size of the set and n is the size of the longest word in the set (See [START_REF] Maier | The complexity of some problems on subsequences and supersequences[END_REF]). This algorithm is still impracticable even when the set is small, as the size of the words plays an important role in the time consumption and the words are commonly large. For this reason, much part of the research is focused on the special case of a set of two words.

The problem is presented as follows: given a word v of size m and a word w of size n, compute the LCS of v and w. A well-known algorithm solves this problem in O(nm) using a dynamic programming strategy: Each instance of the problem can be solved by solving simpler subproblems (usually instances that are smaller in size) that are themselves solvable with simpler subproblems and so on until the instances can be solved trivially. As, a subproblem can appear multiple times, to avoid recomputing the same instance more than once, we memorise the solution of each subproblem and retrieve it when the same subproblem recurs.

A LCS is computed as follows:

• If the rst letter of the LCS is the rst letter of w and v, the rst letter is concatenated with the LCS of the words w[1 :] and v[1 :].

• If the rst letter of the LCS is the rst letter of w but not of v, the LCS of the words w and v[1 :] is computed.

• If the rst letter of the LCS is the rst letter of v but not w, the LCS of the words v and w[1 :] is computed.

• If the rst letter of the LCS is the rst letter of w and v,the LCS compute the LCS of the words w[1 :] and v[1 :] is computed.

We only need two indexes to indicate where we are in the words w and v. As, all subproblems are computed at most once and in constant time, the algorithm runs in O(nm).

Longest Common Subsequence for Permutations.

Problem 30. Given a set S of permutations, the LCS seeks to nd the longest pattern common to all permutations in S.

As with strings, the problem of a set having only two permutations has been a focus of research. However, this condition is not sucient for computing the LCS in polynomial time; other approaches are needed. A possible strategy for solving the problem polynomially is to restrict the set S to be in a certain class. It should be noted that by restraining S to be in a class C, the LCS is also an element of C.

Problem 31. Given C, a class of permutations, given a set of permutation S ⊂ C, the LCS problem seeks to nd the LCS of all permutations in S.

Restricting the Set to the Set of Permutations that are in Bijection with Binary Words

The problem 31 is solvable whenever C is a class of permutations of size n that are in bijection with binary words of size n. Such classes of permutations exist; they include the wedge permutations (as see above), the unimodal permutations (which are the permutations that can be split in one increasing and one decreasing permutation) and the rie shue permutations (which are the permutation that can be partitioned into two increasing subsequence, one above the other).

To compute the LCS over such permutations, the permutations are transformed into binary words. The LCS is then computed over the two binary words, with the positions used in the LCS being tracked. The LCS for the permutations is the subsequence with the elements at same position as the LCS on the binary words. As shown in Section 5.2.1 the algorithm for nding the LCS on words runs in O(mn), but the bijection from permutation to word depends on the class so the whole algorithm runs in max(O(mn), BC) time, where BC is the complexity of the bijection.

Restricting the Set to the Permutations Separable Permutations

A result also exists whenever at least one permutation is a separable permutation, as shown later in this thesis (See section 6.5).

Computing the Longest Wedge Subsequence

Instead of computing any LCS, another strategy for reducing the complexity is, to compute LCS that belongs to a certain class. As demonstrated later in this thesis (see Section 7.5), whenever we want to nd a LCS that is a wedge permutation, there exists a O(n 3 m 3 )-time algorithm where n and m are the size of the permutations.

State of the Art

The results about the LCS of two permutations are summarize in table 5.2.

Superpattern

Denition 32. Given a set S of permutations, a superpattern of S is a permutation that contains all of the permutations in S. O(n 3 m 3 )-time Section 7.5 a wedge permutation of two permutations 1 n and m refer to the size of the two permutations. 2 BC is the complexity of the bijection. We can specify the denition when S corresponds to all of the permutations of a given size. Denition 34. A k-superpattern is a permutation that contains all permutations of size k.

Problem

Example 35. The permutation 25314 is a 3-superpattern.

Lower and Upper Bounds for the size of the Minimal

Superpattern for all Permutations of the same Size

The problem of nding a k-superpattern is trivial, as one can nd a k-superpattern by a direct sum with all of the permutations of size k (which results in a permutation of size kk!). The problem becomes more interesting in its minimisation: Given a size k, compute a k-superpattern with minimal size with respect to other k-superpatterns. This problem can be transformed into a decision problem in which the minimisation factor is replaced by the size of the superpattern and we can play with this value to nd the minimal size required.

Problem 36. Given two integers k and n, the k-superpattern minimisation asks whether a k-superpattern of size n exists.

Example 37. The permutation 25314 is a smallest 3-superpattern. Indeed, the occurrence of the permutation 123 and 321 can only share the element representing the 2, so we need two more elements to represent the 1 and 3 of 123 and two more to represent the 3 and 1 of 321.

The problem was rst introduced by Arratia in 1999 in [START_REF] Arratia | On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern[END_REF]. This article presents a k-superpattern of size k 2 by exhibiting the grid permutation, also known as k-grid permutation (note that the notion of "grid classes of permutation" exists and both notion are dierent, See [START_REF] Albert | Geometric grid classes of permutations[END_REF]). The grid permutation is constructed by iterating over all of the positions (starting at 1) moving to the next position by a step of k and putting the elements in increasing order. More formally, this corresponds to the permutation in which elements at position i have values rk + 1 + q where r and q are the remainder and the quotient of the euclidean division of i -1 by k. See Figure 5.3 for an illustration. It is easy to see that the k-grid permutation contains all permutations of size k. To nd an occurrence of a given permutation σ, the grid permutation is split into k x k squares of the same size. Observing that each square contains one point, we dene each square by its coordinates on the plan, such that the square in the bottom left corner is square (0, 0), the one above it is (0, 1), the one on its right is (1, 0) and so on. From this construction, there exists an occurrence of σ such that each element (i, σ[i]) is represented by the point in the square at coordinate (i, σ[i]). See Figure 5.4 for the occurrence of the permutation 132 in the 3-grid permutation.

In the same paper, Arratia also provided the lower bound of (k/e) 2 for the size of a k-superpattern by an enumerative argument on the number of permutations of size k.

A more rened result concerning the minimal size of k-superpattern was later provided by Eriksson et al. who showed in 2007 in [START_REF] Eriksson | Dense packing of patterns in a permutation[END_REF] that a k-superpattern of size 2k 2 /3 exists; moreover, if k tends to innity, then a k-superpattern of size k 2 /4 exists. They also demonstrated that there exists a permutation that contains every permutation of size k or its inverse of size k 2 /2. In 2009, Miller stated in [45] that a k-superpattern of size (k + 1)k/2 exists.

The general problem of superpatterns (in permutation) that is, when the set S can be anything has to our knowledge not been studied. Nevertheless, some results can be found when some constraints are added to the set, these results are presented in the following section.

Superpattern for Rie-Shue Permutations

We have examples of rened results whenever constraints are put on the set. In 201 3, Wismath and Wol exhibited in [START_REF] Bannister | Small Superpatterns for Dominance Drawing[END_REF] a superpattern of size 2k for the rie-shue permutations of size k. The rst result was obtained by remarking that any rie-shue permutation can be partitioned into two increasing subsequences such that the elements of increasing subsequence are below the element of the other subsequence. This leads to the construction of a permutation by pair of elements: Each time we add an element that can be part of the below increasing subsequence and an element that can be part of the above increasing subsequence. This gives us the permutation 1(k)2(k + 1)3(k + 2) . . . k(2k). See Figure 5.5 for an example.

It should be noted that the elements of a rie-sue permutation can be partitioned into two sets, thus, one can transform a rie-shue permutation into a binary words; nding a superpattern for a rie-shue permutation of size k is the same as nding a binary word that contains every binary words of size k. This formulation makes it clear that the word formed of 01 repeated k times contains all binary words of size k. This result can be extended to every class that is in bijection with binary words.

Superpattern for 321-Avoiding Permutations

In [START_REF] Bannister | Small Superpatterns for Dominance Drawing[END_REF], Wismath et al. also present a superpattern for the 321-avoiding permutations of size O(k 3/2 ).

Superpattern for 213-Avoiding Permutations

In 2014, in [START_REF] Bannister | Superpatterns and Universal Point Sets[END_REF] Wismath et al. also prove that there exists a superpattern of size k 2 /4 -Θ(k) for all of the permutations avoiding 213 of size k and provide a superpattern for some proper subclasses of the 213-avoiding permutation.

State of the Art

The results on the superpattern problem are summarize in the tables 5.6 and 5.7.

Shue

The (rie) shue of a deck of cards involves starting with a sorted deck, cutting it into two parts and then reforming the deck by randomly selecting a card from the bottom of one of the two parts and putting this card on top of the newly formed deck. The mathematical denition only takes from the last step of the (rie) shue. We provide the general denition of a shue and extend it to the permutation. We rst explain one notation. Given a letter a and a set of words S we refer to aS as the set in which we concatenate the letter a to every word in S. Denition 38. Given two words v and w, the shue of v and w, (noted

v ¡w) is the set v[0](v[1 :] ¡ w) ∪ w[0](v ¡ w[1 :]).
This correspond to the set of words that we can obtain from merging the words u and w, by choosing letters randomly from u or w.

Example 39. aa ¡ bb = {aabb, abab, abba, baab, baba, bbaa}

Word Shues

Shue in relation to words was rst introduced by Eilenberg and Mac Lane in [START_REF] Eilenberg | On the groups h(π, n), i[END_REF]. Later on, Prodinger and Urbanek in [START_REF] Prodinger | Innite 01-sequences without long adjacent identical blocks[END_REF] studied a special case of shue called the perfect shue (denoted in the article), which corresponds to the unique word created by picking letters from two words in an alternating manner. In their article, the authors present some properties of a perfect shue. They rst introduce the notion of square word (although they do not name it). Denition 40. A square word w is a word such that there exists a word v such that w ∈ v ¡ v. Some notable results surrounding the shue in words are that it can be decided, in polynomial time whether a word u is in the shue of v and w (see [START_REF] Manseld | On the computational complexity of a merge recognition problem[END_REF] and [START_REF] Van Leeuwen | Ecient recognition of rational relations[END_REF]), and that the problem of deciding whether a word w such that a word u is the shue of word w with itself exists . The latter result is more interesting to us given its similarities to permutation. The problem turns out to be NP-complete (see [START_REF] Buss | Unshuing a square is NP-hard[END_REF] and [START_REF] Rizzi | On recognizing words that are squares for the shue product[END_REF]).

For an overview of the problem, see [START_REF] Henshall | Shuing and unshuing[END_REF] and [START_REF] Restivo | The Shue Product: New Research Directions[END_REF].

Shue for Permutations

We extend the notion of shue for words to that of shue for permutations. This operation was introduced as the supershue by Vargas in [START_REF] Vargas | Hopf algebra of permutation pattern functions[END_REF], and denoted by ¡. In this thesis, we use the notation suggested by Giraudo and Vialette, as these authors present the only result that we are aware of (See [START_REF] Giraudo | Unshuing Permutations[END_REF]).

π ∈ σ 1 • σ 2 .
The recognising shue problem is sometimes referred as the unshuing problem. Although the denition of shue for permutations is complicated, the recognizing shue for permutation problem can be formulated in another way to remove the use of shue for permutations. Problem 43. Given the permutations σ 1 , σ 2 and π, the recognising shue for permutation problem asks whether there exists an occurrence of σ 1 and σ 2 in π that do not share any elements and use every element of π.

While no result exists concerning the recognising shue problem, a result to the related problem of recognising a square shue can be found. Problem 44. Given the permutations σ and π, the recognising square shue for permutation problem asks whether π ∈ σ • σ.

This problem is of interest, as it is strongly related to another problem that naturally arises in the context of PPM . This problem is deciding whether the PPM problem for parameter n -k is FPT. (recalling that the PPM problem is FPT for parameter k [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF]).

In [START_REF] Giraudo | Unshuing Permutations[END_REF], Giraudo and Vialette showed that the recognising square shue for permutations is NP-complete. It is worth mentioning that they put in relation the recognising shue for binary words as similar to the recognising shue for permutation over the wedge permutation ({231, 213}-avoidance permutation); as such, any results for either problem can be applied to the other. It should be noted that [START_REF] Aoki | Expected length of longest common subsequences of two biased random strings and its application[END_REF] claims that recognising shue for binary words is NP-complete but without proof. Thanks to this relation, we can apply the algorithm to detect whether u is in the shue of v and w, to decide whether a wedge permutation π is in the shue of two wedge permutations σ 1 and σ 2 . Result Reference Deciding whether a permutation [START_REF] Giraudo | Unshuing Permutations[END_REF] is a square shue for permutation is NP-complete Deciding whether a separable permutation Section 6.4 π of size n is in the shue of two separable permutations σ 1 of size k and σ 2 of size l can be done in O(nk 3 l 2 ) time and O(nk 2 l 2 ) space Figure 5.10 Results on deciding whether a permutation is a shue of two permutations.

Recognising the Shue of two Separable Permutations

We will see later, in this thesis (in Section 6.4), that an algorithm to decide whether a separable permutation π is in the shue of two separable permutations σ 1 and σ 2 also exists.

State of the Art

The results on deciding whether a permutation is a shue of two permutations are summarize in the table 5.10.

Chapter 6

Separable Permutations

This chapter is devoted to separable permutations, which is one of the rst avoiding class studied. It appears in [START_REF] Bose | Pattern matching for permutations[END_REF] which is the rst paper that provides results on PPM. This class is also a generalisation of the rst avoiding class studied: the 213-avoiding permutations. A 213-avoiding permutation can be characterised by the fact that it can be sorted by a unique stack. Moreover, it appears that a separable permutation can be sorted by an arbitrary number of stacks (See [START_REF] Avis | On pop-stacks in series[END_REF]). We introduce the following denition of a separable permutation. Denition 45. The set of separable permutations is the set of (2413, 3142)avoiding permutations.

We start by presenting the structure of a separable permutation needed for this chapter. In Section 6.2, we revisit the polynomial-time algorithm of Ibarra [START_REF] Ibarra | Finding pattern matchings for permutations[END_REF] for the PPM problem and propose a simpler dynamic programming approach. In Section 6.3 we focus on the case in which both the pattern and the target permutation are separable. Section 6.4 is concerned with presenting an algorithm to test whether a separable permutation is the disjoint union of two given (necessarily separable) permutations. In Section 6.5, we revisit the classical problem of computing a longest common separable pattern as introduced by Rossin and Bouvel [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF] and propose a slightly faster yet still not practicable algorithm. Finally, in Section 6.6, we show that the PPM problem is polynomial-time solvable for bivincular separable patterns. To the best of our knowledge, this is the rst time the PPM problem is proven to be tractable for a generalisation of separable patterns. All the results in this chapter can also be found in [START_REF] Neou | Pattern matching for separable permutations[END_REF].

The Structure of Separable Permutations

Substitution Decomposition

We present in this section the substitution decomposition. Any permutation is decomposable using the operation of substitutions. Especially, decomposition of a separable permutations has a remarkable structure. We begin by giving a denition of the operation of substitution. Denition 46. Given a permutation π of size n and n permutations π 1 , π 2 , . . ., π n , the substitution of π 1 , π 2 , . . ., π n in π, noted π[π 1 , π 2 , . . ., π n ], is the permutation that can be split into n dierent rectangles R 1 , . . ., R n such that:

• Each element π[i] is associated with the rectangle R i .
• Every pair of rectangles is comparable, that is, one is on the left of and below the other one.

• For every rectangles R i and R j , R i = R j , R i is on the left of R j if and only if i < j.

• For every rectangles R i and R j ,

R i = R j , R i is below R j if and only if π[i] < π[j].
• For every rectangle R i , the elements contained in R i are an occurrence of π i .

For example 132 [123,4321,[START_REF] Avis | On pop-stacks in series[END_REF] is the permutation 123987645. It should noted that a unique decomposition (called the canonical decomposition) for any permutation exists when considering substitution in simple permutations, which are permutation that contains no (contiguous) sequence such that the values of the sequence form an interval (See [START_REF] Albert | Simple permutations and pattern restricted permutations[END_REF] for more details on substitutions). When considering the canonical substitution decomposition, a separable permutation can be dene as follows.

Denition 47. A separable permutation is an increasing permutation or a decreasing permutation or it is the canonical substitution of π 1 , π 2 , . . . and π n in π, where π is either the increasing or decreasing permutation and π 1 , π 2 , . . . and π n are separable permutations.

It should be noted that direct an skew sum are special cases of substitution. Indeed

π 1 ⊕ π 2 is equivalent to 12[π 1 , π 2 ] and π 1 π 2 is equivalent to 21[π 1 , π 2 ].
In the following, we focus in decomposition in direct and skew sum.

:] = π[2 : i] ⊕ π[i + 1 :] or π[2 :] = π[2 : i] π[i + 1 :]. We focus on the case in which π[2 :] = π[2 : i] ⊕ π[i + 1 :
] and prove that π is decomposed into a direct sum of two separable permutations which is the other case in which π[2 :] = π[2 : i] π[i + 1 :] can be dealt by following the same idea or using an argument based on the complement of a permutation.

We start by discussing the value of the leftmost element if π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] is below (resp. above) any element of π[i + 1 :], then π = π[: i] ⊕ π[i + 1 :], where π[: i] and π[i + 1 :] are separable permutations which is the claim.

If it is not true, we show that there exists an index j such that every element of π[: j] is below π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] and every element of π[j + 1 :] is above π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF]. This supports our claim, as π would be written as π = π[: j] ⊕ π[j + 1 :]. Suppose that such j does not exist; in other words, at least one element (namely π[i 3 ]) is above π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] and between two elements π[i 2 ] and π[i 4 ] which are below π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF]. This can be expressed as follows:

1 < i 2 < i 3 < i 4 , π[i 2 ] < π[1] < π[i 3 ] and π[i 4 ] < π[1] < π[i 3 ]. Moreover, any element to the left of π[i] is a candidate for i 2 . Indeed, any element to the left of π[i] is below π[1]. As π[i 2 ] is to the left of π[i] and π[i 4 ] is to the left of π[i] we have that π[i 2 ] < π[i 4 ]. As such, 1 < i 2 < i 3 < i 4 and π[i 2 ] < π[i 4 ] < π[1] < π[i 3 ], which implies that π[i 1 ]π[i 2 ]π[i 3 ]π[i 4
] is an occurrence of 2413 which is not possible. This is the main structure that we use for the separable permutation. This result yields a strong recursive denition of separable permutations that allows us to use an algorithm that treats the two parts separately. A separable permutation can be seen as two rectangles, one to the right and below/above the other. More than one decomposition may exists for the same separable permutation. For example, the permutation 214365 can be decomposed into 21 ⊕ 4365 and 2143 ⊕ 21.

Denition 49. Given a separable permutation, the sign of the decomposition refers to whether the permutation is decomposed into direct or skew sum.

Largest Decomposition in Sum

The direct and skew sums are associative operations, which implies that π 1 ⊕ (π 2 ⊕ π 3 ) can be written as π 1 ⊕ π 2 ⊕ π 3 . The consequence of this for separable permutations is that one separable permutation may have more than one decomposition (as said above). Moreover, some brackets are useless. To avoid theses situations, we consider a special decomposition that contain no useless bracket, that is when the operator inside an operand (if any) is the same as the operator of this operand. This has for consequence that the decomposition become unique. Moreover, this decomposition can be identied (from all the decompositions) as the one with the most operands, thus the name of largest decomposition. For example, the permutation 214365 is decomposed into 21 ⊕ 21 ⊕ 21.

Remark 50. Given π and its largest decomposition π 1 ⊕ . . . ⊕ π i ⊕ . . . ⊕ π , all sub-permutations π 1 , π 2 , . . . , π are decomposed into a skew sum. Indeed, if that were not the case, a pair of bracket would be useless.

Computing the Decomposition of a Separable Permutation

Computing the simple decomposition. This can be realised using the following algorithm. The rst step is to decide whether the permutation is decomposed into a direct or a skew sum. To do so, the leftmost element and rightmost elements are compared. If the leftmost element is smaller than the rightmost, the permutation is decomposed into a direct sum; if not, it is decomposed into a skew sum. The next step depends on the decomposition. If the permutation is decomposed into a direct sum, an index (they may be more than one) is sought such that the LRMax is bigger to the RLMin. The permutation is then split at the index, creating the left and the right part. Otherwise, an index (they may be more than one) is sought such that the LRMin is smaller than the RLMax, The permutation is then split at the index, creating the left and the right part. This can be archived by computing the LRMax and RLMin for each index and comparing the value. if the permutation is decomposed into a direct sum then

for each index i in π do if LRM axima[i] > RLM inima[i] then return that π = π[: i -1] ⊕ π[i :]; else continue ; else for each index i in π do if LRM inima[i] < RLM axima[i] then return that π = π[: i -1] π[i :]; else continue ;
It should be noted that the permutation is decomposed into a direct sum if and only if the leftmost element is below the rightmost element. This algorithm is based on the fact that if the permutation is decomposed into a direct sum, than the maximum element of the permutation on the left is smaller than the minimum of the permutation on the right (noting that the left rectangle is below the right rectangle).

Another algorithm computes an entire decomposition. We rst introduce the notion of a break, which happens when two adjacent elements are not contiguous. For example, in the permutation 123654978, the break are 36, 49 and 97.

The algorithm creates a decomposition (treated as a word) while reading the permutation from left to right stopping at each break. One diculty is when a break happens to decide whether what we are about to read is part of the same rectangle or a new rectangle. For example, in the permutation 321654987, 49 is a break, 321654 is a complete rectangle and 987 is a new rectangle. But in the permutation 654987321, 49 is a break, but 987 is in the same rectangle as 654. The idea is to create a new rectangle at each break, but at the next break, we have to check whether what we are currently reading is part of the previous rectangle; this is done by checking whether the current and previous rectangles form a contiguous set of elements (which is a characteristic of a rectangle). If the current rectangle is not part of the previous one, we need to keep it in a stack, and continue the procedure. If it is, we create a new rectangle (by merging the previous and current one), so we also need to check whether the new rectangle is part of the previous one.

Algorithm 2:

Data: A separable permutation π Result: A decomposition of π as a word

R c = π[1] ; stack = ∅ ; for each index i of π starting with 2 do if R c ∪ {π[i]} is a contiguous set then R c .
R c = (R p ⊕ R c ) ; else R c = (R p R c ) ; push R c in the stack ;
It should be noted that this algorithm returns a word representing a decomposition, in which each rectangle is encoded within a pair of parentheses.

Computing the largest decomposition from a simple decomposition

This algorithm is quite natural: Whenever we have π 1 ⊕ (π 2 ⊕ π 3 ), we want to write π 1 ⊕ π 2 ⊕ π 3 . This correspond to remove any useless parenthesis. Remember that the parenthesis are useless the operator of the operand (where the parenthesis are from) is the same as the operator associated to this operand. More formally, the algorithm considers the decomposition as a word (as given in the previous algorithm). It should be noted that the word is composed of 3 parts: a prex, then the sign (of the decomposition) and nally a sux. The prex and sux start with an opening parenthesis and end with a closing parenthesis and they are well-balanced for parentheses, that is the word contain the number of opening parenthesis as closing parenthesis and every prex of the word contain at least more opening parenthesis than closing parenthesis. Moreover they are decompositions of separable permutations. We rst need to obtain the sign of the decomposition. To do so, we need to know when the prex end, this can be done by computing the rst well-balanced word (for parentheses) of the decomposition, the next letter of the word computed is the sign of the decomposition. Note that we obtain the 3 parts describe above: the word computed is the prex, we have the sign and what is right to sign is the sux. A decision needs to be made as to whether to remove the parentheses of the prex and the sux. We remove parentheses if and only if the sign of the prex (or the sux), is the same as the sign of the decomposition.

Binary Trees

This section present the representation of separable permutation as a tree. A tree consists of nodes (which are usually labelled to contain informations). A nodes is related to another one by the relation of being a child or parent, such that every nodes have one parent except for a specic node called the root and each node is a child or a parent to at least another node. Moreover the relations cannot create a circle, that is there exists no sequence of nodes such that each pair of nodes are related (with the same relation for all pairs) and the last node is related to the rst node.

We represent a tree by drawing every node in a top-down representation, starting with the root. We represent the child relation with a edge between the two related nodes. It should be noted that edges can be understood as the child relation when reading the tree from top to bottom, or as the parent relation when reading the tree from bottom to top. See Figure 6.1 for an example of tree.

We say that a node C is a descendant of a node P if and only if there exists a sequence of node, such that P is the rst element and C is the last element, and each node is the child of the node to its left. We can also say that P is an ancestor of C. Moreover we say that a node is a leaf if and only if it has no child. We refer the reader to [START_REF] Knuth | The art of computer programming[END_REF] Chapter 2 Section 3 for more informations on tree.

We consider a special case of tree. Binary trees add the condition that each node has two children or is a leaf. A denition of a separating tree was given by Bose, Buss, and Lubiw in [START_REF] Bose | Pattern matching for permutations[END_REF]: a rooted binary tree in which the elements of the permutation appear (in permutation order) at the leaves of the tree, and in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive node in which all descendants of the left child are smaller than all descendants of the right node, or a negative node in which all descendants of the left node are greater than all descendants of the right node. See Figure 6.1 for an illustration. Each subtree of a separating tree may be interpreted as itself representing a smaller separable permutation, whose element values are determined by the shape and sign pattern of the subtree. Constructing a separating tree of a separable permutation is in linear time and space [START_REF] Bose | Pattern matching for permutations[END_REF].

Remark 51. The labels on the leaves do not matter, as only the structure of the tree matters. However, for the sake of comprehension, the leaves are labelled to their corresponding element in the permutation.

A Separable Permutations Seen as a Tree

As the binary tree decomposition appears to be not well suited for our needs, we must use the notion of compact separating tree. Instead of considering only a binary tree, we consider a tree in which each node has the largest number of children possible. Informally, in a compact separating tree we strive for every node to have as many children as possible. Such a tree can be formally dene by modifying the following denition: a rooted tree in which the elements of the permutation appear (in permutation order) at the leaves of the tree, in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive node in which all descendants of a child are smaller than all descendants of another child to its right, or a negative node in which all descendants of a child are greater than all descendants of another child to its right. See Figure 6.1 for an example. We denote a separating tree representing π by T π . Moreover, for every node v of T σ , we let σ(v) stand for the sequence of elements of σ stored at the leaves of the subtree rooted at v.

Remark 52. In such a tree, two nodes (one being the child of the other) never share the same sign. Indeed, if two nodes are father and child, then the father can adopt the children of this particular child, which violates the denition.

Remark 53. In such a tree, two nodes (one being the child of the other) never share the same sign. Indeed, if two nodes are father and child, then the father can adopt the children of this particular child, which violates the denition.

Computing the Tree of a Separable Permutation

Computing the compact separating tree from a separating tree A simple linear time post-processing can be used to produce the decomposition tree from a binary separating tree: As long as the separating tree contains a positive node whose father is also a positive or a negative node whose father is also negative, we simply suppress that node, and let all of its children be adopted by their grandfather in proper order.

Relations Between the Decomposition in Direct and Skew Sums and the Separable Tree

The decomposition in direct/skew sums exhibits a recursive structure. As a result, we can represent a separable permutation by a binary tree. The tree representing the separable permutations with a unique element is the tree a with a unique node. Any other separable permutations are represented by a binary tree. The root encodes what operation (direct or skew sum) the permutation is decomposed into, with the tree's left and right children representing the operation's left and right permutation, respectively. This corresponds to the denition of a separable tree. The relation between the decomposition and the separating tree can be summarised as follows:

π = e π = π 1 ⊕ π 2 π = π 1 π 2 e - T π1 T π2 + T π1 T π2
The same idea applies to the compact separating tree. Each node encodes which operation the permutation is decomposed into, and each child of this node represents a "subpermutation", in proper order, which means that the rst child represent the rst "subpermutation", the second child the second "subpermutation" and so on. More formally, if π has for the largest decomposition into direct sum π = π 1 ⊕ . . . ⊕ π , then the (unique) compact separating tree of π is the tree with a positive root and with the compact separating tree of π 1 as rst child, the compact separating tree of π i as i th child, and the compact separating tree of π as th child. The same is true if π is decomposed into a skew sum. See Figure 6.3 for an example. It should be noted that when π is decomposed into direct (resp. skew) sums it forms a stair up (resp. down) of rectangles.

Detecting a Separable Pattern

This section is devoted to examining of PPM problem whenever we add the condition that the pattern is a separable permutation. Our contribution is that we reduced the space consumption of the best algorithm so far to O(n 3 logk) from O(kn 3 ), where k is the size of the pattern and n is the size of the text.

Problem 54. Given a separable permutation σ of size k and a permutation π of size n, we wish to determine whether σ occurs in π.

In what follows, we present a polynomial time algorithm, in time and space, to solve this problem. The next subsections break the algorithm down. We rst introduce the basic idea of the algorithm. Thereafter we show how Ibarra strengthened this idea. Finally, we demonstrate how we improved the algorithm of Ibarra.

Simple Algorithm

A simple algorithm arises from the decomposition of a separable permutations into direct/skew sums. The following property is the main idea of this algorithm.

Property 55. Given a permutation such that σ = σ l ⊕ σ r (resp. σ = σ l σ r ), if we are given an occurrence o l of σ l in a permutation text π and an occurrence o r of σ r in a permutation text π, such that every element of o l is at the left and below (resp. left and above) of the elements o r , then the subsequence formed by the concatenation of o l and o r is an occurrence of σ in π.

Proof. We focus on the case in which σ = σ l ⊕ σ r . Suppose that the concatenation is not an occurrence, which means that at least two elements are not "well" ordered. By hypothesis, these two elements cannot both be in o l (as o l is a "correct occurrence") or o r (as o r is a "correct occurrence"); as such, one element is in o l and the second is in o r . Remark that the correct order is that the two elements are increasing, as one represent an element in σ l , the other an element in σ r , and by the denition of a direct sum, every element in σ l is below σ r . This means that the two problematic elements are in decreasing order. However, as by hypothesis every element in o l is above every element of o r this is a contradiction., The case in which σ = σ l σ r follows the same idea.

An algorithm that follows this property computes occurrences for the left and for the right operands such that the two rectangles of the occurrences are comparable and in order, which depends on whether the permutation is decomposed into direct or skew sum. This implies a recursive algorithm: For every way to split the text into a left and right parts, we rst decide whether the text's left part has an occurrence of the pattern's left part and whether the text's right part has an occurrence of the pattern's right part. This is done recursively, with each recursive call receiving a text and a pattern of a size smaller than the original problem. At some point, we have a trivial problem (which corresponds to the case in which σ = 1). The algorithm still needs to assure that the occurrences are comparable and in order. This is done while splitting the text: We always split the pattern into its left and right parts, but we split the text into two part such that the rectangle of the left part is at the left and below (right larger rectangle r g and that r s contains an occurrence of a pattern, then r g also contains an occurrence of that pattern. This implies that the algorithm loses computational time by testing r s and r g . To be optimal, it should only test r g . More practically, for the case in which σ = σ l ⊕ σ r , this has the following consequence:

1. If the pair of rectangles are not next to each other then we can nd a rectangle containing the left rectangle (resp. right rectangle) such that this rectangle and the right rectangle (resp. and the left rectangle) are pairs of rectangle that are compatible. This means that the rst pair of rectangle is not optimal. In other words, we always want a pair of rectangle that are next to each other. More formally, if the top right corner of the left rectangle is (x, y) then the bottom left corner of the right rectangle need to be (x + 1, y + 1).

2. Given that we receive the rectangle ((i, lb), (j, ub)) (See Remark 56), the left rectangle is always contained in (or equal to) the rectangle composed with bottom left corner (i, lb) and with the same top right corner as the left rectangle. This means that if the left rectangle is not equal to the rectangle latterly described, then the pair of rectangle is not optimal. In other words, we always want a left rectangle that has the same bottom left corner as the rectangle received. More formally, the bottom left corner of the left rectangle is (i, lb). In the same fashion, the top right corner of the right rectangle is (j, ub).

Thank to these remarks, the iteration of pairs of rectangles is done over the following set: {((i, lb), ( , π[ ])), (( + 1, π[ ] + 1), (j, ub)

) | i ≤ ≤ j}
To understand the time and space complexity of this algorithm, it is important to note the following elements:

1. The set of all possible instances of this algorithm can be enumerated. This gives us a bound on the number of times that the algorithm is used and thus a time complexity for the algorithm. The algorithm takes as input a permutation π with a rectangle (See Remark 56) and a permutation σ.

The number of dierent rectangles is O(n 4 ) as any indexes (( * , * ), ( * , * ) can have a value between 1 and n. For σ, the algorithm only receives a subpermutation of σ. The problem lies in enumerating all the dierent subpermutations σ. The subpermutations of σ are a left or right part of a decomposition or σ. We use the analogy between a subpermutation and a node of a tree to count the number of subpermutations. This number is related to the number of nodes of a binary tree. Remember that any subpermutation of a decomposition in a direct/skew sum of a separable permutation can be associated with a node on a separable tree. So there are at much subpermutation that there are nodes. In addition, each element is associated with a leaf, which means that there are k leaves. As such, the tree theory tells us that if a binary tree has k leaves then the tree has at most k + k -1 nodes. The maximal number of subpermutations of σ is thus O(k). So the algorithm has O(kn 4 ) dierent instances.

2. Each instance iterates over every pair of rectangle. Based on the Remark 60, the iteration consists of an iteration of an index between the values i and j. As i and j represent the index of π, the minimal value of i is 1 and the maximal value of j is n, in the worst case the index goes from 1 to n. Moreover, any other operations are done in constant time, which means, that an instance is computed in O(n) time in the worst case.

As we must remember any instance computed (See Remark 57), we need O(kn 4 ) space. Moreover, as O(kn 4 ) dierent instances of the problem exist and each instance takes at most O(n) time to compute, the algorithm runs in O(kn 5 ) time.

Algorithm of Ibarra

This subsection is devoted to presenting the work of Ibarra in [START_REF] Ibarra | Finding pattern matchings for permutations[END_REF].

Proposition 61. There exists an algorithm that decides whether σ occurs in π in O(kn 4 ) time and O(n 3 k) space.

The idea of the algorithm of Ibarra follows the same idea presented in the previous subsection. However, it uses another trick to reduce the number of dierent instances to compute, reducing the number of dierent instances from O(kn 4 ) to O(kn 3 ), which obliviously results in the complexity given in the latter proposition.

In the case where σ = σ l ⊕ σ r , while splitting the rectangle of π into R r and R l , if a R r is given σ r , R l need to be the largest possible to increases the chance of containing an occurrence of σ l . Indeed if R l is as large as possible, it contains all other rectangles; as such instead of checking whether each of these rectangles contains an occurrence of σ l , it is faster to check whether the largest one contains an occurrence. Moreover, given an occurrence of σ r , the occurrence's minimal element can be used as a bottom edge of a rectangle that contain this occurrence and it is the largest top edge possible for this occurrence. Choosing the largest top edge for the right rectangle, allows the left rectangle to be the largest possible. As such, given that σ = σ l ⊕ σ r , we rst split the rectangle vertically. we then focus on computing all of the occurrences of σ r contained in the right rectangle. In all of these occurrences, we choose the one with the largest minimal element (for the reason explained above). This element can now be used as a bottom edge for the right rectangle.

To use a recursive algorithm (as before), we need the bottom edge's value, which can be done using the return value. The return value needs to encode the largest bottom edge's value. We use the following convention to determine whether an occurrence exists: If the value returned is 0, then no occurrence exists. if not, an occurrence exists and the value returned is the value of the largest bottom edge. useless, which means that we can "forget" them and release some space. It should be noted that, we use the notation of a node to represent σ, as it is better suited for the explanation. The policy for achieving the memory spearing is as follows:

• All problems for a same node v are solved together, and their solutions are maintained in the memory until the problems for the parent of v have also been solved. At that point, the memory used for node v is released.

• We use a modied depth-rst search (noted as DFS) on T σ : For every node v with two children, we rst process its largest child (in terms of the number of nodes in the subtree rooted at that child), then the other child, and nally v itself.

We claim that the above procedure yields a O(n 3 log k) space algorithm and initially expand our DFS algorithm to what is known as the White-Gray-Black DFS [START_REF] Cormen | Introduction to algorithms[END_REF]. First, we mark all vertices white. When we call dfs(u), we mark u to be gray. Finally, when DFS(u) returns, we mark u to be black. Provided by this colour scheme, at each step of the modied DFS, we may partition T σ into a white-gray subtree (all nodes are either white or gray) and a forest of maximal black subtrees (all nodes are black and the parent of the root, if it exists, is either white or gray). Our space complexity claim is now reduces to proving that, at any time of the algorithm, the forest contains at most O(log k) maximal black subtrees. Let h σ be the height of T σ , and consider any partition of T σ into a white-gray subtree and an non-empty forest T b of maximal black subtrees. The following property easily follows from the (standard) DFS colour scheme.

Claim 63. For every 1 ≤ i ≤ h σ , there exists at most two maximal black subtrees in T b whose roots are at height i in T σ . Furthermore, if there are two maximal black subtrees in T b whose roots are at height i in T σ (they must have the same parent), then T b contains no maximal black subtree whose root is at height j > i in T σ .

According to Claim 63, and aiming at maximising |T b |, we may focus on the case in which T b contains one maximal black subtree whose root is at height i, 1 ≤ i < h σ , in T σ (if T b contains one maximal black subtree whose root is at height 0 in T σ then |T b | = 1), and T b contains two maximal black subtrees whose roots are at height h σ in T σ (these two maximal black subtrees reduce to size-1 subtrees). The claimed space complexity for the dynamic programming algorithm (i.e., |T b | = log(k)) now follows from the fact that we are using a modied DFS algorithm where we branch the largest subtree rst after having marked a vertex gray. Indeed, the maximal black subtree whose root is at height Problem 64. Given a separable permutation σ of size k and a separable permutations π of size n, we wish to determine whether σ occurs in π.

In what follows, we will show that there exist a polynomial time algorithm, in time and space, to solve the Problem 64.

Best algorithm so far

We can strive for more ecient solutions when both π and σ are separable permutations since, we can construct in linear time the two separating trees T π and T σ . However, It turns out that the binary separating trees are not well suited to handle this task. We instead need compact separating trees. We adopt the convention that a compact separating tree of a separating tree T π is denoted Tπ .

To introduce the best algorithm so far, we need a denition of the tree inclusion. The problem is dened as follows: Given two ordered and labelled trees T and T , can T be obtain from T by deleting nodes? (Deleting a node v corresponds to removing all edges incident to v and, if v has a parent u, replacing the edge from u to v by edges from u to the children of v. In other words, the father of the node deleted adopt the children of the node deleted, with respect to the original order of the children. See Figure 6.4.) This problem has recently been recognised as an important query primitive in XML databases. This is the rationale for considering compact separating trees stems from the following property. This problem is interesting to us because it can be used to solve the PPM when both the text and the pattern are separable permutations.

To do so we need two modications:

1. We need to change the denition of the deletion: When we delete a node, we have the following rule for the adoption. The father of the deleted node adopts one child of the deleted node; moreover, if it adopts a node (remark that the father of the deleted node and the child of the deleted node share the same sign), then the father adopts all the children of this node. See Figure 6.5 for the dierent outcomes of a deletion. Intuitively, a subtree of a tree represents a subpermutation of the permutation represented by the tree, and the former denition of deletion can create a tree which do not represent a subpermutation. See Figure 6.6 an example.

T + L -v + a b c R delete(T, v) + L c R delete(T, v) + L a b R Figure 6.5
The possible eects of removing a node. Note that the leaves are label with letters for the sake of comprehension.

T + 1 -v 1 1 1 delete(T, v) + 1 1 1 1 Figure 6.6
The eect of a "normal" removing a negative node with a positive father, the permutation encoded in the left tree is 1324, whereas the permutation encoded in the right is 1234.

permutation, as the leaf's labels are included for the sake of readability (see Remark 51).

Remark 65. The denition of deletion can be seen easily in a plot of a permutation. A rectangle should be rst selected (which corresponds to choosing the node to delete). Another rectangle within this rectangle should then be selected and other rectangles removed.

Property 66. Deleting a node from a compact separable tree constructs another compact separable tree. Moreover, the permutation represented by the new compact separable tree is a subpermutation of the original permutation.

Proof. First note that any child of a deleted node can be seen as a root of a compact separable tree. As such, adopting all children of a child a of deleted node implies that the children are already decomposed into the largest nodes possible, which means that the deletion creates a compact separable tree. Now remark that deleting a node corresponds, in the permutation, to removing some elements represented by this node. As such, clearly yields a subpermutation.

Property 67. Let π and σ be two separable permutations. Then, σ occurs in π if and only if the compact separating tree Tσ is included into the compact separating tree Tπ .

Proof. This is a direct consequence of the previous property.

Kilpeläinen and Manilla [START_REF] Kilpeläinen | Ordered and unordered tree inclusion[END_REF] presented the rst polynomial time algorithm using quadratic time and space for the tree inclusion problem. Since then, several improved results have been obtained for special cases in which T and T have a small number of leaves or small depth. However, in the worst case, these algorithms still use quadratic time and space. The best algorithm is provided by Bille and Gørtz [START_REF] Bille | The tree inclusion problem: In linear space and faster[END_REF] who presented an O(n T ) space and

O   min    l T n T l T l T log log n T + n T n T n T log n T + n T log n T     
time algorithm, where T (resp. T ) is the tree representing π (resp. σ ), n T (resp. n T ) denotes the number of node of T (resp. T ) and l T (resp. l T ) denotes the number of leaves of T (resp. T ).

However, all ecient solutions developed so far for the tree inclusion problem result in very complicated and hard-to-implement algorithms. For example, the main idea of the algorithm presented in [START_REF] Bille | The tree inclusion problem: In linear space and faster[END_REF] is to construct a data structure on T supporting a small number of procedures, called the set procedures, on subsets of nodes of T .

Our Solution

We propose here a dierent solution that is less eective in time and space than the above algorithm.

Proposition 68. An O(n 2 k) time and O(nk) space algorithm to nd an occurrence of a separable pattern of size k in a separable permutation of size n exists.

We need to consider four cases in the algorithm, depending on the decompositions of σ and π. For these cases, we begin with a brute force algorithm that tries all possible subsequences, and reduce the number of subsequences to test.

The next paragraph deals with the case where σ and π are decomposed with the same sum.

Property 69. Given the largest decomposition π = π 1 ⊕. . .⊕π π and the largest decomposition σ 1 ⊕ . . . ⊕ σ σ , no occurrence of σ i can be split into two or more rectangles of π.

Proof. If the occurrence of σ i can be split into two or more rectangles of π then σ i can be decomposed into a direct sum, which is not possible as σ i is part of the largest decomposition of the direct sum.

From this property, we know that, in an occurrence of σ in π, any rectangle π i contains no, one or more than one rectangle of σ. Given an occurrence, taking all of the rectangles of π that contain at least one rectangle of σ, forms a subsequence of rectangles π P1 , . . . , π Pm of π 1 , . . . , π π . For each of those rectangles, we associate the set of rectangles that this rectangle contains in the occurrence, and form a sequence of pair (π i , P i ) in which the permutation represented by the set P i occurs in π i . It should be noted that the P i forms an ordered partitioning of the rectangles of σ. Finding such a sequence is enough to prove that an occurrence of σ exists in π.

Lemma 70. Given the largest decomposition π = π 1 ⊕ . . . ⊕ π π and the largest decomposition σ = σ 1 ⊕ . . . ⊕ σ σ , if there exists a sequence (π i , P i ) such that the permutation represented by the set P i occurs in π i and all the P i forms an ordered partitioning of the rectangles of σ, then σ occurs in π.

Proof. If such a sequence does not yield an occurrence, there exist at least two elements σ[i] and σ[j] such that their matchings do not have the same order as σ[i] and σ[j]. Without a loss of generality, we can suppose that i < j. Suppose that σ[i] and σ[j] are contained in one rectangle/two rectangles that is/are contained in P i , by denition of the sequence the permutations represented by P i occur in π i which means that every elements are well-ordered, so this cannot happen. We are left with the case in which σ[i] and σ[j] are contained in rectangles that are contained in P i and P j . As the elements are contained in dierent sets, it can be deduced that they are in dierent rectangles. Moreover, as σ is decomposed into a direct sum, P i is on the left and below P j ; as such, σ[i] < σ[j]. The hypothesis indicates that the matchings of σ[i] and σ[j] do not have the same order, but their matchings are contained in π i and π j . Moreover, π i is on the left and below π j as π is decomposed into a direct sum. Their matching thus cannot have a dierent order, which shows that the hypothesis does not hold. Such sequences therefore contain an occurrence. obtain a sequence with either no dierence between the sequence computed by the algorithm or where the dierence starts after the pair corresponding to p i . By iterating this process, we can create a solution that does not dier from the sequence computed by the algorithm; the algorithm thus computes a solution, which is a contradiction.

The next paragraph deals with the case where σ and π are decomposed with dierent sums. We focus on the case in which π is decomposed into a skew sum and σ is decomposed in direct sum.

Proposition 71. Given the largest decomposition π = π 1 . . . π π and the largest decomposition σ 1 ⊕ . . . ⊕ σ σ = σ, σ occurs in π if and only if there exists π i such that σ occurs in π i .

This proposition claims that σ can only occur in a rectangle of π. This can easily be explained visually; σ forms a "stair up", if it is contained in more than one rectangle of π, as the rectangles of π form a "stair down", the "stair up" of σ would be cut.

Proof. For the backward implication, remark that π i occurs in π, and σ occurs in π i , as such, σ occurs in π. For the forward implication, suppose that the leftmost element of σ is matched to an element of π α and that the rightmost element of σ is a matched to an element of π β . The leftmost element of σ is below the rightmost element of σ, as σ is formed by an increasing sequence of rectangles; however every element of π α is above every element of π β , as π is formed by a decreasing sequence of rectangles. Such an occurrence is thus not possible.

This proposition leads directly to the following algorithm for deciding whether σ occurs in π.

Algorithm 6:

Data: The sequence of rectangles π = π 1 , . . . , π π of the largest decomposition of π Data: σ Result: Whether σ occurs in π for every rectangle in π 1 , . . . , π π do if σ occurs in the current rectangle then return that σ occurs π ; return that σ does not occur in π ;

It should be noted that, that Algorithm 5 and 6 call each other. We modify this algorithm for the purpose of computing the p required for the rst algorithm: Instead of computing whether σ occurs in π, the algorithm computes the rightmost rectangle such that the σ 1 , . . . , σ i occurs in π. If this rectangle is σ σ then we can conclude that σ occurs in π. for every rectangle in π 1 , . . . , π π do tmp = The rightmost σ i such that σ 1 , . . . , σ i occurs in the current rectangle ;

if tmp is at the right of r then r = tmp ; return r ;

We also need to modify Algorithm 5 to compute tmp: Instead of returning the solution or that no solution exists, the algorithm returns the last rectangle added in p.

We have described two algorithms that can be used to compute every case possible; as a result we have an algorithm for deciding whether σ occurs in π. We still need to prove the complexity claim. To do so, we introduce a closed set of entries for the algorithms, and, use dynamic programming to ensure that each algorithm is only called at most once for each element of the closed set. This gives us a bound to the number of times that each algorithm is called. The rst algorithm is called to compute tmp for the third algorithm or to decide whether σ occurs in π. In both cases, it only requires two rectangles: σ i and π j . The third algorithm is called to compute p for the rst algorithm or to decide whether σ occurs in π. The second case requires two rectangles σ and π; however the rst case requires a π i and a sequence of rectangles, especially s = σ i , . . . , σ σ . Nonetheless, the last rectangle of the sequence is always the rightmost rectangle of the decomposition. We use a well-suited structure to represent the rectangles so that we can represent the sequence with only one rectangle. A compact separable tree lls the requirement. Indeed, remember that, in the tree representation, a node represents a rectangle and the decomposition of a rectangle is represented by the children of the node. This means that the node representing σ i , . . . , σ σ has the same father. Thus from the node representing σ i , the node representing σ σ is its rightmost brother. To summarise, each algorithm only needs to take one node from the compact tree of σ and one node from the compact tree of π. As the tree of π has O(n) nodes and the tree of σ has O(k) nodes, O(nk) entries are possible for the algorithms. Finally, each algorithm is computed in O(n) times, as they only involve doing an iteration over the rectangles of π. The algorithm thus runs in O(kn 2 ) time and O(kn) space.

Deciding the Union of a Separable Permutation

This subsection is devoted to shuing permutations. Given three permutations (namely π, σ and τ ), the problem is to decide whether π is the disjoint union of two patterns that are order-isomorphic to σ and τ , respectively, in notation π ∈ σ ¡ τ . For example 937654812 is the disjoint union of two patterns that are order-isomorphic to 2431 and 53241, as can be seen in the highlighted form 937654812.

Proposition 72. Given three separable permutations π of size n, σ of size k and τ of size , there exists an O(nk 3 2 ) time and O(nk 2 2 ) space algorithm for deciding whether π is the disjoint union of two patterns that are orderisomorphic to σ and τ , respectively.

Proposition 72 become more interesting if we observe that the complexity of the problem is still open if we do not restrict the input permutations to be separable [START_REF] Giraudo | Unshuing permutations, 12th Latin American Theoretical Informatics Symposium (LATIN)[END_REF].

First, if π is a separable permutation and π ∈ σ ¡ τ , then σ and τ are also separable. As such, we consider the non-trivial case in which σ and τ are separable.

Given that π is a separable permutation we denote by π π the rightmost rectangle of the permutation's largest decomposition (especially π = π 1 ⊕ . . . ⊕ π π ). Moreover, we let π(i, j) be π i ⊕ . . . ⊕ π j .

Proof. Consider the following family of subproblems: Given a separable permutation π and a sequence of its largest decomposition π(i π , j π ), a separable permutation σ and a sequence of its largest decomposition σ(i σ , j σ ) and a separable permutation τ and a sequence of its largest decomposition τ (i τ , j τ ), we want to check whether π(i π , j π ) is the shue of σ(i σ , j σ ) and τ (i τ , j τ ). We notate this as follows:

S(π(i π , j π ), σ(i σ , j σ ), τ (i τ , j τ )) = T rue if π(i π , j π ) ∈ σ(i σ , j σ ) ¡ τ (i τ , j τ ) F alse otherwise. By denition π ∈ σ ¡ τ if and only if S(π(1, π ), σ(1, σ ), τ (1, τ )) is true.
Base.

The base cases are when either σ = 1 or τ = 1. Then, if π is also a leaf then the problem is true; otherwise the problem is false, as elements will be left unmatched in π.

• If π and σ are the trivial permutation of size 1 and τ has no element then S(π(1, 1), σ(1, 1), ∅) = T rue.

• If π and τ are the trivial permutation of size 1 and σ has no element then S(π(1, 1), ∅, τ (1, 1)) = T rue.

• Otherwise the problem is F alse.

Reduction.

Two instances of the problem can represent the same problem. Especially when one of the arguments represents an unique node, we replace this node by all of its children. This happens only when i * = j * , where * ∈ {π, σ, τ }.

• If i π = j π then S(π(i π , i π ), σ(i σ , j σ ), τ (i τ , j τ )) = S(π iπ (1, πi π ), σ(i σ , j σ ), τ (i τ , j τ )) • If i σ = j σ then S(π(i π , j π ), σ(i σ , i σ ), τ (i τ , j τ )) = S(π(i π , j π ), σ iσ (1, σi σ ), τ (i τ , j τ )) • If i τ = j τ then S(π(i π , j π ), σ(i σ , j σ ), τ (i τ , i τ )) = S(π(i π , j π ), σ(i σ , j σ ), τ iτ (1, τi τ ))

Recurrence

The idea of the recursion is to split σ(i σ , j σ ) and τ (i τ , j τ ), in every possible way in π(i π , j π ). Each splitting yields two dierent instances of the problem. We dierentiate two classes of instances: The rst class can be characterised by the fact either σ or τ is empty. This is the best case, as it corresponds to deciding whether σ (or τ , depending on which one is empty) is an occurrence of π; we let the other class contain all instances that do not belong to the rst one. In all cases, both instances are smaller in size, especially the size of the text permutation is reduced and the size of the rst or second pattern is reduced. The recursion uses Property 71 and Lemma 70 to make a "smart" splitting.

• In cases in which π(i π , j π ) represents a direct sum decomposition, σ(i σ , j σ ) represents a direct sum decomposition and τ (i τ , j τ ) represents a skew sum decomposition. Note that according to Property 71, if τ (i τ , j τ )) occurs in π(i π , j π ) then it occurs in a unique rectangle, in particular, we can consider the rst rectangle of π(i π , j π ) for the occurrence of τ (i τ , j τ ) and handle the case accordingly. As such, π iπ can contain an occurrence of τ (i τ , j τ )) and some part of an occurrence of σ(i σ , j σ ), an occurrence of τ (i τ , j τ )) and no occurrence of σ(i σ , j σ ) or nothing of τ (i τ , j τ )) and some part of an occurrence of σ(i σ , j σ ).

The case in whichs π iπ contains nothing cannot occur, as we want every element of π to be used in an occurrence. In those three cases, what is left of σ and τ has to occur in π(i π + 1, j π ), which yields us the following solution:

S(π(i π , j π ), σ(i σ , j σ ), τ (i τ , j τ )) = j σ <jσ (S(π(i π , i π ), σ(i σ , j σ ), τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), σ(j σ + 1, j σ ), ∅)) OR (S(π(i π , i π ), ∅, τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), σ(i σ , j σ ), ∅)) OR j σ <jσ (S(π(i π , i π ), σ(i σ , j σ ), ∅) ∧ S(π(i π + 1, j π ), σ(j σ + 1, j σ ), τ (i τ , j τ )))
• In cases in which π(i π , j π ) represents a direct sum decomposition, both σ(i σ , j σ ) and τ (i τ , j τ ) represent a skew sum decomposition. Based on Property 71, σ(i σ , j σ ) occurs in a unique child of π(i π , j π ) and τ (i τ , j τ ) occurs in a unique child of π(i π , j π ). Moreover, as every element must be used in an occurrence, π(i π , j π ) cannot have more than two rectangles. In other words, if π(i π , j π ) has more than two rectangles, then this instance is false. In addition, if π(i π , j π ) has two rectangles σ(i σ , j σ ) occurs π iπ , and τ (i τ , j τ ) occurs π jπ , or σ(i σ , j σ ) occurs π jπ and τ (i τ , j τ ) occurs π iπ :

S(π(i π , j π ), σ(i σ , j σ ), τ (i τ , j τ )) = S(π(i π , i π ), σ(i σ , j σ ), ∅) ∧ S(π(j π , j π ), ∅, τ (i τ , j τ )) OR S(π(i π , i π ), ∅, τ (i τ , j τ )) ∧ S(π(j π , j π ), σ(i σ , j σ ), ∅)
• If π(i π , j π ), σ(i σ , j σ ) and τ (i τ , j τ ) represent direct sum decompositions then according to Lemma 70, π iπ contains some part of the occurrence of τ (i τ , i τ ) and some part of the occurrence of σ(i σ , j σ ), some part of the occurrence of τ (i τ , i τ ) and no element of an occurrence of σ(i σ , j σ ), no element of an occurrence of τ (i τ , i τ ) and some part of the occurrence of σ(i σ , j σ ), the occurrence of τ (i τ , i τ ) and some part of the occurrence of σ(i σ , j σ ), the occurrence of τ (i τ , i τ ) and no element of an occurrence of σ(i σ , j σ ), some part of the occurrence of τ (i τ , i τ ) and the occurrence of σ(i σ , j σ ) or no element of an occurrence of τ (i τ , i τ ) and the occurrence of σ(i σ , j σ ).

In all of these cases, what is left occurs in π(i π + 1, j π ).

S(π(i

π , j π ), σ(i σ , j σ ), τ (i τ , j τ )) = j σ <jσ j τ <jτ S(π(i π , i π ), σ(i σ , j σ ), τ (i τ , j τ ))∧S(π(i π +1, j π ), σ(j σ +1, j σ ), τ (j τ +1, j τ )) OR j σ <jσ S(π(i π , i π ), σ(i σ , j σ ), ∅) ∧ S(π(i π + 1, j π ), σ(j σ + 1, j σ ), τ (i τ , j τ )) OR j τ <jτ S(π(i π , i π ), ∅, τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), σ(i σ , j σ ), τ (j τ + 1, j τ )) OR j τ <jτ S(π(i π , i π ), σ(i σ , j σ ), τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), ∅, τ (j τ + 1, j τ )) OR S(π(i π , i π ), σ(i σ , j σ ), ∅) ∧ S(π(i π + 1, j π ), ∅, τ (i τ , j τ )) OR j σ <jσ S(π(i π , i π ), σ(i σ , j σ ), τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), σ(j σ + 1, j σ ), ∅) OR S(π(i π , i π ), ∅, τ (i τ , j τ )) ∧ S(π(i π + 1, j π ), σ(i σ , j σ ), ∅)
• All others cases can be aliate with one of the above cases, such that it can be solved by applying the idea of that case.

We are left with proving the complexity claim. As before we use a dynamic programming strategy so that we only need to compute each instance of the problem once. As such, we only need to identify the number of dierent entries possible for the problem to determine its complexity. In this paragraph, let be the size of τ . Without a loss of generality, we can suppose that < k. At rst, it seems that the problem has n 2 k 2 d 2 cases: For every permutation, we associate two rectangles of its decomposition.

However, one of the three pairs has redundant information. As, the size of π(i π , j π ) must be equal to the size of σ(i σ , j σ ) plus the size of τ (i τ , j τ ), given σ(i σ , j σ ), τ (i τ , j τ ), π and i π , we can deduce j π . It should be noted that j π may not exist, as the size of σ(i σ , j σ ) plus the size of τ (i τ , j τ ) may not exactly equal the size of a π(i π , j π ); however, in such a case, we can immediately say that π is not a shue. We thus have O(nk 2 2 ) dierent cases to compute. This strategy implies that for every permutation, we have to compute the size of every π(i π , j π ) possible, which can be pre-computed in O(n 2 ) time and takes O(n 2 ) space in the memory.

The worst case for this algorithm is when π contains elements of occurrences for both σ and τ . In this case, we must iterate every j σ , i σ ≤ j σ ≤ j σ and every j τ , i τ ≤ j τ ≤ j τ possible. However, we can deduce j σ from π(i π , i π ), τ (i τ , j τ ), σ and i σ (as above). As a result we only need to iterate every j τ , i τ ≤ j τ ≤ j τ possible. Finally, each recursive problem is solved in constant time by dynamic programming. Computing one case thus takes at most O( ) time, which gives us an O(nk 2 3 ) time and O(nk 2 2 ) space algorithm.

Finding a Maximum Size Separable Subpermutation

The longest common pattern problem for permutations is nding the largest permutation that occurs in each input permutation, which is intended to be the natural counterpart to the classical LCS problem. Rossin and Bouvel [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF] provide an O(n 8 ) time algorithm for computing the largest common separable pattern that occurs in two permutations of size (at most) n, one of these two permutations being separable. This problem was further generalised in [START_REF] Bouvel | Longest common separable pattern between permutations[END_REF], which demonstrates that the problem of computing the largest separable pattern that occurs in k permutations of size (at most) n is solvable in O(n 6k+1 ) time and O(n 4k+1 ) space. It should be noted that the latter problem is NP-complete for unbounded k, even if all input permutations are actually separable. The following proposition improves upon the algorithm of Rossin and Bouvel [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF].

Proposition 73. Given a permutation of size n and a separable permutation of size k, the largest common separable pattern that occurs in the two input permutations can be computed in O(kn 6 ) time and O(n 4 log k) space.

Proof. For clarity of exposition, we begin by considering the problem of computing the largest separable pattern that occurs in a single permutation π. We consider the following family of subproblems: For every two i, j ∈ [n] with i ≤ j and every lower and upper bound lb, ub ∈ [1, 2, . . . , n] with lb ≤ ub, we have the subproblem P i,j,lb,ub , where the semantic is as follows:

P i,j,lb,ub = max{|s| : s is a subsequence of π[i, j], reduction(s) is separable, and every element in s is in the interval [lb, up]}.

We show that this family of problems is closed under induction.

• Base: We have two cases.

If i = j, then

P i,i,lb,ub = 1 if lb ≤ π[i] ≤ ub, 0 otherwise.
If lb = up, then

P i,j,b,b = 1 if there exists ι ∈ [i, j] such that π[ι] = b, 0 otherwise.
•

Step: Here i < j, lb < ub, and we must decide whether the optimum P i,i,lb,ub is achieved with a positive or negative root node. Thus P i,j,lb,ub = max P + i,j,lb,ub , P - i,j,lb,ub , where (Hypothesis of a positive node)

P + i,j,lb,ub = max{P i,ι-1,lb,b-1 + P ι,j,b,ub : i < ι ≤ j and lb < b ≤ ub}.
(Hypothesis of a negative node)

P - i,j,lb,ub = max{P i,ι-1,b-1,ub + P ι,j,lb,b : i < ι ≤ j and lb < b ≤ ub}.
This implies an O(n 6 ) time and O(n 4 ) space algorithm for nding the largest separable pattern that occurs in a permutation of size n. The next step is to consider the problem of nding a longest separable pattern that occurs in two given permutations (that may not be separable themselves) [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF]. Let π be a permutation of size n. For every i, j ∈ [n] with i ≤ j and every ub, lb ∈ [n] with lb] ≤ up, we let π[i, j, lb, up] stand for the subsequence obtained from π[i, j] by trimming away all elements above lb or below up. Then, let π 1 and π 2 be two permutations of S n . We consider the following family of subproblems: For every i 1 , j 1 , lb 1 , ub 1 ∈ [n] with i 1 ≤ j 1 and lb 1 ≤ ub 1 , and every i 2 , j 2 , lb 2 , ub 2 ∈ [n] with i 2 ≤ j 2 and lb 2 ≤ ub 2 , we have the subproblem P i1,j1,lb1,ub1,i2,j2,lb2,ub2 whith the following semantic: P i1,j1,lb1,ub1,i2,j2,lb2,ub2 = max{|s| : s is a pattern occurring in both

π 1 [i 1 , j 1 , lb 1 , ub 1 ] and in π 2 [i 2 , j 2 , lb 2 , ub 2 ]}
It is easy to see that this family of subproblems is closed under induction and yields an O(n 12 ) time and O(n 8 ) space algorithm for nding the size of largest separable pattern that occurs in two permutations of size (at most) n. This is a slight improvement compared to [START_REF] Bouvel | Longest common separable pattern between permutations[END_REF], which proposes an O(n 13 ) time and O(n 9 ) space algorithm.

The outlined approach can be extended to a polynomial time algorithm for a xed number of input permutations (as shown in [START_REF] Bouvel | Longest common separable pattern between permutations[END_REF]). However, in practice the complexity of this solution is already prohibitive for just two sequences. Therefore, rather than further extending this approach, we focus on underlining how it encompasses other natural problems. Indeed, following Bouvel and Rossin [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF], we consider the problem of computing a longest separable pattern that occurs in two input permutations of size at most n, one of these two permutation being separable. For this precise problem, Bouvel and Rossin provide an O(n 8 ) algorithm. We consider the following family of subproblems: Given σ a separable permutation and T σ its separating tree. For every node v of T σ , every two i, j ∈ [n] with i ≤ j, and every lower and upper bounds lb, ub ∈ [n] with lb ≤ up, we have the subproblem P v,i,j,lb,ub , with the following semantic: P v,i,j,lb,ub = max{|s| :s is a common subsequence of v and π[i, j] with all values in the interval [lb, ub].

We show that this family of problems is closed under induction.

• Bases: We have three base cases:

If i = j] then P v,i,i,lb,ub = 1 if lb ≤ π[i] ≤ ub, 0 otherwise. If lb = ub] then P v,i,j,b,b = 1 if there exists ι ∈ [i, j] such that π[ι] = b, 0 otherwise. If v is a leaf then P v,i,j,lb,ub = 1 if there exists ι ∈ [i, j] such that lb ≤ π[ι] ≤ ub, 0 otherwise.
•

Step: Here i < j, lb < ub, and we let v L and v R stand for the left and right children of v, respectively.

If v is a positive node then

P v,i,j,lb,ub = max i<ι≤j max lb<b≤ub P v L ,i,ι-1,lb,b-1 + P v R ,ι,j,b,ub .
If v is a negative node then

P v,i,j,lb,ub = max i<ι≤j max lb<b≤ub P v L ,i,ι-1,b-1,ub + P v R ,ι,j,lb,b .
The above description implies an O(kn 6 ) time O(kn 4 ) space algorithm for computing the largest common separable pattern that occurs in two permutations of size (at most) n, one of these two permutations being separable, with thus improves on Rossin and Bouvel [START_REF] Rossin | The longest common pattern problem for two permutations[END_REF]. The memory can be reduced to O(n 4 log k) using the approach detailed Section 6.2.3.

Vincular and Bivincular Separable Patterns

This subsection is devoted to vincular pattern and BVP. We prove that detecting a vincular or bivincular separable pattern in a permutation is polynomial time solvable. To the best of our knowledge, this is the rst time the PPM problem is proven to be tractable for a generalisation of separable patterns. Since a vincular pattern is a BVP, we focus on BVP.

The algorithm of Section 6.2 cannot be used to nd an occurrence of a BVP as we do not have any control over the position and the value of matching elements.

Proposition 74. Given a permutation π of size n and a bivincular separable pattern σ of size k, there exists an O(kn 6 ) time and O(kn 4 ) space algorithm to decide whether σ occurs in π.

Given a BVP with a separable permutation σ, and a subsequence σ , we dene the bivincular permutation σ as the bivincular permutation with the element of σ , with the top line of σ where we remove the elements not in σ and with bottom line the elements of the node where m and m+1 are underlined if and only if m and m + 1 are element of σ and m and m + 1 are underlined in σ. Moreover, In particular (remember that σ(v) represents the subsequence embedded in the node v) we represent by σ(v) the BVP formed by the subsequence σ(v).

• if σ[i]
The idea of the algorithm is to use the separable tree of σ to nd an occurrence. To nd an occurrence of σ, we need to nd an occurrence for the (permutation embedded in) its left child and the (permutation embedded in) its right child such that those two occurrences are "compatible" with each other. That is, the occurrences must be contained in rectangles such that the rectangle of the occurrence of the left child is to the left of the rectangle of the occurrence of the right child. In addition, one has to be above the other, depending whether σ is decomposed in a direct or skew sum. This is sucient for nding an occurrence of σ, but not of σ. Indeed, the constraints on values and positions are not respected.

Moreover, given that σ = σ α ⊕ σ β , if the topmost, bottommost, leftmost, and rightmost elements of σ α (resp. σ β ) are respectively on the top, bottom, left, and right edges of the rectangle of the occurrence of σ α (resp. σ β ) and if the two rectangles are consecutive on the x-coordinate (with the rst minimal rectangle ending at x and the second minimal rectangle starting at x + 1), then the matchings of the rightmost element of σ α and the matching of the leftmost element of σ β are consecutive in index. In the same fashion, if the rectangles are consecutive on the y-coordinate (with the rst minimal rectangle ending at y and the second minimal rectangle starting at y + 1), then the matching of the topmost element of σ α and the matching of the bottommost element of σ β are consecutive in value.

The above remark allows us address the constraint value between the bottommost element of σ β and the topmost element of σ α and the constraint position between the leftmost element of σ β and the rightmost element of σ α .

Moreover, an occurrence of σ α (resp. σ β ) takes care of all constraints on the value and position of the elements in σ α (resp.σ β ), except for its topmost and rightmost (resp. bottommost and leftmost) elements. The only constraints left are thus on those elements, but we can resolve them by positioning the rectangle correctly.

If u is a leaf such that σ[i] = σ(u), then we write σ(u+1) to represent σ[i+1] and σ(u -1) to represent σ[i -1].

The pattern matching problem with bivincular permutation σ can be solved by the following family of subproblems: Given T σ the compact separating tree of σ. For every node v of T σ , every two i, j ∈ [n] with i ≤ j, every lower and upper bound lb, ub ∈ [n] with lb ≤ ub, that form a rectangle with left bottom corner (i, lb) and right top corner (j, ub), we wish to decide whether the rectangle contains an occurrence of σ(v). This gives us the following notation:

PMB v,i,j,lb,ub =         
T rue if there exists an occurrence of the BVP σ(v) in π where all elements are contained in the rectangle ((i, lb), (j, ub)).

F alse otherwise

By abuse of language, we say that σ(v) occurs in ((i, lb), (j, ub)). This problem can be solved by the following induction: the elements of the occurrence of σ α are left of and below the elements of the occurrence of σ β , then there exists an occurrence of σ in π. More formally, we have to check every case possible to determine whether the elements really occur on the edges.

For the constraints on positions and values, intuitively, whenever we have σ(v)σ(v ) and w as the deepest ancestors of v and v , σ(v) is matched to the right edge of the left rectangle and σ(v ) is matched to the left edge of the right rectangle so that σ(v) and σ(v ) are consecutive in index. Likewise, if (σ(v))σ(v ), σ(v) is matched to the top edge of the left rectangle and σ(v ) is matched to the bottom edge of the right rectangle so that σ(v) and σ(v ) are consecutive in value. See Figure 6.9). Position Constraints. Three types of position constraints are added by BVP .

• If σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF], then the leftmost element of σ must be matched to the leftmost element of π (σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] occurs in π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] in an occurrence of σ in π). Remark that the leaf v such that σ(v) = σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] is the leftmost ancestor of r σ . Note that the rectangle of a left child shares the same left edge as the rectangle of its father (by induction); plus, this is solved in the base case, which asks for the matched element to be on its left edge. Finally note that the main problem has x = 1 for its left edge.

• The condition σ[n σ ] follows the same idea as the condition σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF]. • If σ(v)σ(v ) (and thus σ(v + 1) = σ(v ) and σ(v) = σ(v -1) ), then the index of the occurrences of σ(v) and σ(v ) must be consecutive. In other words, if σ(v) occurs in π[j] then σ(v ) must occur in π[j + 1]. Let w be the rst common ancestor of v and v and w L be the left child of w and w R be the right child of w. First note that v is the rightmost ancestor of w L . As such, the rectangle of v shares the same right edge as the rectangle of w L , plus v is the leftmost ancestor w R and thus the rectangle of v shares the same left edge as the rectangle of w R . Moreover, these cases are solved as base cases, which ask for the element matching v to be on its right edge, and for the element matching v to be on its left edge. Finally, remark that the pair of rectangles of two brothers is consecutive in the x-coordinate (by induction).

Before we delve into the value constraints, it is important to highlight a property.

Property 75. Given a node v and a leaf u, such that σ(u) is the maximal (resp. minimal) element of σ(v), if v occurs in ((i, lb), (j, ub)), then there exists i ≤ ι ≤ ι ≤ j, lb ≤ b ≤ ub and u occurs in ((ι, b), (ι , ub)) (resp. ((ι, lb), (ι , b))).

In other words, if v occurs in a rectangle R and u is the leaf with the maximal element of σ(v), then there exists an occurrence of u included in a rectangle that shares the same top edge as R (see Figure 6.10). Especially if PMB v,i,j,lb,ub is true then PMB u,ι,ι ,b,ub is true.

Proof. We focus on supporting the assertion in the case in which σ(u) is the maximal element of σ(v); the other case can be dealt by following the same idea or using a complement's argument. Suppose that the assertion is false. If the rectangle of u cannot have the same top edge as the rectangle of v a rectangle in between exists; in other words, there exists a value larger than σ(u) which is not possible.

Value Constraints. Three types of value constraints are added by BVP .

• If σ(v) (and thus σ(v) = 1), then the minimal value of σ must occur in the minimal value of π. According to Property 75, the rectangle of σ(v) has the same bottom edge as the rectangle of σ(r σ ). This is also solved in the base case, which asks the matching element to be on the bottom edge. Finally, the rectangle of r σ has y = 1 as its bottom edge.

• The σ(v) follows the same idea as σ(v).

• If σ(v)σ(v ) (and thus σ(v ) = σ(v) + 1), then the occurrences of σ(v) and σ(v ) must be consecutive. In other words, if σ(v) occurs in π[j] then σ(v ) must occur in π[j] + 1. Let w be the rst common ancestor of v and v . w L be the left child of w and w R be the right child of w. if w is positive, then v is a child of w L and v is a child of w R . First σ(v) is the maximal element of σ(w L ); otherwise, σ(v) and σ(v ) would not be consecutive. According to Property 75, the rectangle of σ(v) has the same top edge as the rectangle of σ(w L ). In addition, σ(v ) is the minimal element of σ(w R ); otherwise, σ(v) and σ(v ) would not be consecutive. Property 75 therefore dictates that the rectangle of σ(v) has the same bottom edge as the rectangle of σ(w R ). Moreover, this is solved in the base case and the base case asks the element matching σ(v) to be on its top edge and the element matching σ(v ) to be on its bottom edge. Finally,the pair of rectangles of two brothers is consecutive in the y-coordinate (by induction). We can prove the case in which if w is negative by following the same idea or a complement's argument.

As such, at the end of the algorithm we can decide whether σ occurs in π. Finally, the algorithm has kn 4 dierent cases, and each case tries every pair of rectangles in constant time (by dynamic programming), which means that each case takes O(n 2 ) time to solve. This gives us a O(kn 6 ) time and O(kn 4 ) space algorithm.

Chapter 7

Wedge Permutations

This chapter focuses on wedge permutations, which are a sub-class of the separable permutations. Wedge permutations have more constraints on their structures than separable permutations, which allows us to reduce the computational time and space of some problem solutions. A formal denition of a wedge permutations is provided below. Denition 76. The set of wedge permutations is the set of (213, 231)-avoiding permutations.

This chapter is organised as follows. We rst describe the structure of a wedge permutation. Section 7.2 is then presents an online linear-time algorithm in the case that both permutations are wedge permutations, whereas Section 7.3 focuses on the case in which only the pattern is a wedge permutation. In Section 7.4, we oer a polynomial-time algorithm for a bivincular wedge permutation pattern. Section 7.5 then considers the problem of nding the longest wedge permutation pattern in permutations. Property 78. π is a wedge permutation of size n if and only if for

1 ≤ i ≤ n, π[i] is an RLMax or RLMin element.
Proof. It should be noted that every sub-permutation π[i :] is a wedge permutation. As a wedge permutation and given property 77, π[i] is either the topmost or the bottommost element of π[i :], which is similar to saying that π[i] is an RLMax or RLMin element.

Property 79. The sub-permutation formed with all of the RLMax elements of a wedge permutation is a decreasing subsequence. In the same fashion, the set of RLMin elements is an increasing subsequence. Proof. Indeed, each element that is to the left of and above the next RLMax element is by denition an RLMax element. See Figure 7.1.

Property 80. Any RLMax element is below any RLMin element in a wedge permutation.

Proof. Suppose that this is not the case. By denition, any RLMax element is the topmost element of all the elements to its right. As such, any RLMin element above an RLMax element must be on its left. However, the denition of an RLMin element dictates that no element comes below, so we have a contradiction.

Remark 81. We can draw a horizontal line (passing thought the rightmost element) on a wedge permutation such that the upper half contains only a decreasing subsequence and the lower half contains only an increasing subsequence. This shapes the permutation as a >, which is why it is called a wedge permutation. See Figure 7.1.

Bijection with Binary Words

As a consequence of Property 78, a wedge permutation can be partitioned into three sets: the set of RLMax elements, the set of RLMin elements and the rightmost element, which can be both a RLMax element and a RLMin element. The partition gives a bijection B between the set of wedge permutations of size n with elements 1, . . . , n and the set of binary words of size n -1. The word w which corresponds to π is the word in which each letter at position i represents whether π[i] is a RLMax or RLMin element. We also extend this transformation to the subsequence of wedge permutations. Given a subsequence s, the binary word B(s) is the word in which the letter at position i represents whether s[i] is a RLMax or RLMin element. For any permutation, guring out whether an element is a RLMax or RLMin element requires one to read the whole permutation from left to right, starting from the element's position.

Property 82. Let π be a wedge permutation and 1 ≤ i < n. Then,

1. π[i] is a RLMin element if and only if π[i] < π[i + 1] and 2. π[i] is a RLMax element if and only if π[i] > π[i + 1].
Proof. We focus on proving the case of an RLMin element, as the case of a RLMax element follows the same idea. The forward implication is trivial, as the element is an RLMin element and it is the bottommost element of all the elements to its right. In particular, an RLMin element is below the next element; as such, if π[i] is an RLMin, then π[i] < π[i + 1]. For the backward implication, if π[i] is not an RLMin element, then there exists an element π[j] such that π[i] > π[j] and i < j. In other words, we have that π

[j] < π[i] < π[i + 1], and i < i + 1 < j which is equivalent to saying that π[i]π[i + 1]π[j]
is an occurrence of 231, which is impossible, as π is a wedge permutation.

Decomposition of a Wedge Permutations into Factors

We need to consider a specic decomposition of σ into factors. We split the permutation into maximal sequences of consecutive RLMin and RLMax elements, which are respectively called an RLMin factor and an RLMax factor. This corresponds to splitting the permutation between every pair of RLMin-RLMax and RLMax-RLMin elements (see Figure 7.1). For the special case of a wedge permutation, this also corresponds to splitting the permutation into maximal sequences of elements consecutive in value. We label the factors from right to left. It should be noted that the rightmost element can be both an RLMin and RLMax element. We follow the convention that it is the same type as the element before it for the factorisation, so that the rst factor (that is the rightmost factor) always contains at least two elements. For example, σ = 123984765 is split as 123 -98 -4 -765. Hence, σ = factor(4) factor(3) factor( 2) factor(1) with factor(4) = 123, factor(3) = 98, factor(2) = 4 and factor(1) = 765. See Figure 7.1.

Both π and σ are Wedge Permutations

This section presents a fast algorithm for deciding if σ occurs in π in the case that both π and σ are wedge permutations.

Proposition 83. Let π and σ be two wedge permutations. It can be decided whether π has an occurrence of σ in linear time.

We rst need the following lemma.

Lemma 84. Let π and σ be two wedge permutations. Given a bijection B from the wedge permutations of size n to the binary word of size n -1. Then, π contains an occurrence of σ if and only if there exists a subsequence t of π such that B(t) = B(σ).

Proof. The forward direction is obvious. We prove the backward direction by induction on the size of σ: If B(t) = B(σ), then t is an occurrence of σ. The base case is a pattern of size 2. Suppose that σ = 12 and thus B(σ) = RLMin. Let t = π i1 π i2 , i 1 < i 2 , be a subsequence of π such that B(t) = RLMin; this reduces to saying that π i1 < π i2 , and hence that t is an occurrence of σ = 12 in π. A similar argument shows that the lemma holds for σ = 21. Next, assume that the lemma is true for all patterns up to size k ≥ 2. Let σ be a wedge permutation of size k + 1 and let t be a subsequence of π of size k + 1 such that Remark 93. The algorithm in [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] runs in O(n log log n). However, as we add an upper bound and a lower bound to compute every dierent instance, in our algorithm the whole computation is done in O(n 3 loglogn) time.

Remark 94. Given that the pattern starts with an RLMin (resp. RLMax) element, if the occurrence starts at the left edge of the rectangle (i.e.. π[j] is part of the occurrence), then as the leftmost element of the pattern is an RLMin (resp RLMax) value, and every element of the occurrence is above (resp. below) it, π[j] can be used as a lower (resp. upper) bound and thus as the bottom (resp. top) edge of the rectangle. In the algorithm, instead of nding any occurrence we nd an occurrence that start at the left edge. This has two consequences on the algorithm:

1. We can remove one argument corresponding to the bottom or top edge, as it only depends on π[i]. We remove the top edge if σ i is an RLMin factor and the bottom edge if σ i is an RLMax factor. To do so, the algorithm takes the left and right edge of the rectangle and a bound. The bound represents the top edge of the rectangle if σ i is an RLMin factor and the bottom edge, otherwise.

2. The denition of the problem also changes. Instead of looking for any occurrence on the rectangle, we want an occurrence that starts at the left edge of the rectangle. It should be noted that the occurrence must start at the left edge of the rectangle. We need to modify this part reect in account the latter change (this corresponds to changing Algorithm 9). Thankfully, the algorithm in [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] takes this into account by It actually computing the longest increasing/decreasing subsequence starting at element π[i]. As a result, we do not need to modify our algorithm. Moreover, as in accordance with Remark 93 we only have one bound, the whole computation is thus done in O(n 2 log log n) time.

Improving the Simple Algorithm

We extend our research to reduce the number of pairs of rectangles that we have to test. The idea is that when deciding whether a rectangle contains an occurrence of a pattern, to split the rectangle, the algorithm rst "cuts" it vertically, to produce two rectangles (with the rst to the left of the second one). The algorithm then decides whether the second rectangle contains an occurrence of the "right part of the pattern". From all of the occurrences that the algorithm nds, it is in our best interest to select the one that is contained in the smallest rectangles possible; this ensures that the rst rectangle is larger and thus contains more elements, so it has a better chance to contain an occurrence of the left part of the pattern. It should be noted that given that the leftmost factor of the pattern is an RLMin (resp. RLMax) factor, the left, right, and top (resp. bottom) edges of the second rectangle are xed. Indeed, it should be recalled that in the algorithm, the second rectangle shares its top (resp. bottom) right corner with the original rectangle which provide the right and top (resp. bottom) edges; moreover the algorithm has already "cut" the original rectangle vertically, which gives the left edge. The "smallest rectangle" can thus only be obtained using the bottom (resp. top) edge, which should be the topmost (resp. However we rst introduce the notation LMEp(s), which stands for the leftmost element position: Suppose that s is a subsequence of S, which means that LMEp(s) is the position of the leftmost element of s in S. For every factor, LMEp(factor(j)) thus stands for the position in σ of the leftmost element of factor(j), for example, LMEp(factor(4)) = 1, LMEp(factor(3)) = 4, LMEp(factor(2)) = 6, and LMEp(factor(1)) = 7. See Figure 7.2 for a representation of every LMEp of each factor.

We also provide the following property to know the position of the topmost and leftmost elements on a wedge permutation.

Property 95. Given a wedge permutation σ if factor(i) is an RLMin (resp.

RLMax) factor the topmost (resp. bottommost) element of factor(i) . . . factor [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] is the leftmost element of factor(i -1).

Simply put, the bottommost element is on the second factor from the left if the rst factor from the left is an RLMax factor; otherwise, the topmost element is on the second factor from the left. See Figure 7.3.

Proof. This lemma states that, given a wedge permutation, if the permutation starts with an RLMin (resp. RLMax) element then the topmost (resp. bottommost) element of this permutation is the rst RLMax (resp. RLMin) element (see Figure 7.3). This is easy to see from the shape of a wedge permutation. Formally, the RLMin elements are below the RLMax elements. The topmost element must thus be the rst RLMax element, which is the leftmost element of factor(i -1).

We also dene S π σ (i, j) as the set of all subsequences s of π[j :] that start at π[j] and are occurrences of factor(i) . . . factor(1).

Lemma 96. Let σ be a wedge permutation and factor(i) be an RLMin (resp.

RLMax) factor σ. Let π be a permutation and s a subsequence of π such that s ∈ S π σ (i, j), and s minimises (resp. maximises) the matching of the leftmost element of factor(i -1). Let s be a subsequence of π such that s ∈ S π σ (i, j) and let t = t s be a subsequence of π that extends s on the right. Assume that t is an occurrence of factor(i + 1) . . . factor(1) such that the leftmost element of factor(i) is matched to π[j]. The subsequence t s is then also an occurrence of factor(i + 1) . . . factor [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] such that the leftmost element of factor(i) is matched to π[j]. Informally, this lemma states that we can replace the rectangle of an occurrence in S π σ (i, j) by another rectangle of an occurrence in S π σ (i, j) such that the second rectangle shares the same edges as the rst one, except for the top edge, which is lower. In particular, the second rectangle can be chosen as the one with the lowest top edge of all rectangles that share the right, bottoms and left edges. More formally, given any occurrence of factor(i + 1) factor(i) . . . factor(1), in which factor(i) is an RLMin (resp. RLMax) factor, we can replace the part of the occurrence where factor(i) . . . factor(1) occurs, by any occurrence that minimises (resp. maximises) the leftmost element of factor(i -1). Indeed, the leftmost element of factor(i -1) is the topmost (resp. bottommost) element of factor(i) . . . factor(1) (see Figure 7.3).

Proof. Let us consider the case in which factor(i) is an RLMin factor. By denition s is an occurrence of σ[LMEp(factor(i)) :]. First of all, remark that t is an occurrence of factor(i + 1). To prove that t s is an occurrence of factor(i + 1) . . . factor(1), we thus need to prove that the elements of t are above the elements of s. Since t s is an occurrence of factor(i + 1) . . . factor(1) it follows that the elements of t are above the elements of s . Moreover, the topmost element of s is below (or equal to) the topmost element of s ; as such, the elements of s are below the elements of t . We use a symmetric argument if factor(i) is an RLMax factor. Lemma 97. Let σ be a wedge permutation, factor(i) be an RLMin (resp.

RLMax) factor and s be a subsequence of π such that s ∈ S π σ (i, j) and it minimises (resp. maximises) the matching of the leftmost element of factor(i -1).

The following statements are equivalent:

• There exists an occurrence of σ in π in which the leftmost element of factor(i) is matched to π[j], and

• There exists an occurrence t of factor( ) . . . factor(i + 1) in π[: j -1] such that ts is an occurrence of σ in π with the leftmost element of factor(i) matched to π[j].

Proof. The backward direction is trivial, and the forward direction follows from Lemma 96.

This lemma goes a step further from the previous one, as it states that if there is no occurrence of σ in π in which the leftmost element of factor(i) is matched to π[j] and such that the leftmost element of factor(i -1) is minimised (resp. maximised), then no occurrence exists at all. Proposition 98. Let σ be a wedge permutation of size k and π be a permutation of size n. It can decided in O(max(kn 2 , n 2 log(log(n))) time and O(n 3 ) space if π contains an occurrence of σ.

Proof. This algorithm is similar to the previous one, as it takes a rectangle and decides whether it contains an occurrence of σ. However, instead of returning true or false, assuming that factor(i) is an RLMin (resp. RLMax) factor the algorithm returns the optimal value of the top (resp. bottom) edge of a rectangle that contain the pattern (or a special value that indicates that no occurrence exists). In the recursion, the computed value of the right rectangle is thus used as the top (resp. bottom) edge of the left rectangle.

We rst introduce a set of values needed to solve the problems. Let LIS π (j, j bound) (resp. LDS π (j, j , bound)) be the longest increasing (resp. decreasing) subsequence in π[j : j ] starting at π[j], with every element of this subsequence being smaller (resp. larger) than or equal to bound. LIS π and LDS π can be computed in O(n 2 log(log(n))) time (see [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF]). LIS π (j, j , bound) (resp. LDS π (j, j , bound)) allows us to decide the existence of an occurrence starting at π[j] of any LRMin (resp. LRMax) factor in the rectangle ((j,π[j]), (j , bound)) (resp. ((j, bound) ,(j , π[j])).

Given an RLMin (resp. RLMax) factor, namely factor(i), of σ and a position j in π, we want the value of the top (resp. bottom) edge of any rectangle with bottom left (resp. top left) corner (j, π[j]) containing an occurrence of factor(i) . . . factor(1) starting at π[j] and minimises (resp. maximises) its top (resp. bottom) edge or a value, which indicates that no occurrence exists in this rectangle. This can be expressed more formally as follows:

• If factor(i) is an RLMin factor, then

PM π σ (i, j) =               
The top edge of any rectangle with bottom left corner (j, π[j]) with right edge n containing an occurrence of factor(i) . . . factor(1) starting at π[j] which minimises the top edge.

Or ∞ if no occurrence exists.

• If factor(i) is an RLMax factor, then

PM π σ (i, j) =               
The bottom edge of any rectangle with top left corner (j, π[j]) with right edge n containing an occurrence of factor(i) . . . factor(1) starting at π[j] which maximises its bottom edge.

Or 0 if no occurrence exists. By denition, there exists an occurrence of σ in π if and only if there exists a j ∈ {1, . . . , n} such that PM π σ ( , j) = 0 and PM π σ ( , j) = ∞ with the number of factors in σ.

We show how to compute, these values recursively.

• If the permutation is reduced to an RLMin (resp. RLMax) factor, then one has to compute the top (resp. bottom) edge of a rectangle that contains an increasing or decreasing subsequence that is the same size or larger than the size of the unique factor starting at π[j]. This case occurs when i = 1:

If factor(i) is an RLMin factor, then

PM π σ (1, j) = min {π[j ] | |f actor(1)| ≤ LIS π (j, j , π[j ])} j ≥j ∪ {∞}.
If factor(i) is an RLMax factor, then

PM π σ (1, j) = max {π[j ] | |f actor(1)| ≤ LDS π (j, j , π[j ])} j ≥j ∪ {0}.
• Otherwise, if factor(i) is an RLMin (resp. RLMax) factor, we split the rectangle into two rectangles R 1 and R 2 such that R 1 is left of and below (resp. left of and above) R 2 . R 1 contains an occurrence of factor(i) starting at j, and R 2 contains an occurrence of factor(i -1) . . . f actor(1) starting at j > j. As mentioned before, we only need to test the pair of rectangles in which the rectangle R 2 has for its left edge j and has the highest bottom (resp. lowest top) edge that contains an occurrence. For R 2 , we thus want a rectangle starting at j , which contains an occurrence of factor(i-1) . . . f actor(i ) starting at j with maximise the bottom (resp. minimise the top) edge. Moreover, we also wish to know the value of the bottom (resp. top) edge to use it as a bound for R 1 so that R 1 is below R 2 . In other words we want PM π σ (i -1, j ). As before, R 1 has to be as large as possible. Moreover, to ensure that R 1 is to the left of and below (resp. to the left and above) R 2 , R 1 must have (j -1, PM π σ (i -1, j ) -1) as its top right corner (resp. (j -1, PM π σ (i -1, j ) + 1) as its bottom right corner ). Finally, in all of the "correct" pairs of rectangles, we need the value of the top (resp. bottom) edge of a rectangle that minimises the top edge (resp. maximises the bottom edge) containing the pair of rectangles. It should be noted that the top (resp. bottom) edge has a value of π[j ] (the matching of LMEp(factor(i -1))). Formally, this can be expressed as follows:

• If factor(i) is an RLMin factor, then The number of factors is bound by k. All instances of LIS π and LDS π can be computed in O(n 2 log(log(n)) time, which takes O(n 3 ) space (see [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF]). There are n base cases that can be computed in O(n) time, which means that; computing all base cases takes O(n 2 ) time. There are kn dierent instances of PM, each taking O(n) time to compute; as such, computing every instance of PM takes O(kn 2 ) time. Computing all of the values therefore takes O(max(kn 2 , n 2 log(log(n))) time. As each value takes O(1) space, the problem takes O(kn 2 ) space, but LIS π and LDS π take O(n 3 ) space.

Bivincular Wedge Permutation Patterns

This section is devoted to the pattern matching problem with bivincular wedge permutation patterns. It should be recalled that a BVP generalises a permutation pattern by being able to force elements in an occurrence to be consecutive in values or/and positions. Intuitively, we cannot use the previous algorithm, as the restrictions on position and value are not managed.

Given a bivincular permutation pattern σ, we let σ[i :] refer to the bivincular permutation pattern, which has for its top line the top line of σ in which we remove the elements before i. Proof. For the rst point, by contradiction, σ[i] + 1 would serve as a `2', σ[i] would serve as a `1' and σ[i + 1] would serve as a `3' in an occurrence of 213.

For the second point, by contradiction, σ[i] -1 would serve as a `2', σ[i] would serve as a `3' and σ[i + 1] would serve as a `1' in an occurrence of 231.

Lemma 100. Let σ be a wedge permutation.

• If m and m + 1 are both RLMin elements, then any element between m and m + 1 (if any) is an RLMax element.

• If m and m -1 are both RLmax elements, then any element between m and m -1 (if any) is an RLMin element.

Proof.

STEP:

We consider three cases for the problem PM σ π (lb, ub, i, j):

• If π[j] /
∈ [lb, ub], then:

PM σ π (lb, ub, i, j) = f alse which is immediate from the denition.

• If π[j] ∈ [lb, ub] and σ[i] is an RLMin element, then: • If σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] appears in σ, then the leftmost element of σ must be matched to the leftmost element of π (σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] is matched to π [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] in an occurrence of σ in π). This constraint is satised by requiring that the occurrence starts at the leftmost element of π: if PM σ π (1, n, 1, 1) is true.

PM σ π (lb, ub, i, j) =                                                        
• If σ[k] appears in σ, then the rightmost element σ must be matched to the rightmost element of π (σ[k] is matched to π[n] in a occurrence of σ in π). This constraint is checked in the base case.

• There are n 3 base cases that can be computed in constant time and kn 3 dierent cases. Each case takes up to O(n) time to compute, which means that computing all cases takes O(kn 4 ) time. As each case takes O(1) space, we need O(kn 3 ) space.

Computing the Longest Wedge Permutation Pattern

Chapter 8

Conclusion

In this thesis we presented polynomial algorithm for the problems of PPM when constraints are added on text and/or the pattern. We also explored the PPM problem with BVP which is the rst positive result on theses pattern. We end this thesis by proposing some interesting questions in relation to PPM. This thesis uses the classication of permutations by avoiding classes. However, other class types exist, especially, the class of grid permutations (See [START_REF] Albert | Geometric grid classes of permutations[END_REF]). The grid class is given by a matrix M of -1, 0 or 1. Informally, in a plot of a permutation, there exists a grid with the same dimensions as the matrix. Intuitively, each brick of this grid is associated with the value in the matrix at the same position as the grid. As such, if the value in the matrix is 1, then the brick contains an increasing sequence, if the value is 0, then the brick contains no element and if the value is -1, then the brick contains a decreasing sequence. See Figure8.1 for an example.

It should be noted that [START_REF] Albert | Geometric grid classes of permutations[END_REF] demonstrates that any grid class can be dene as an avoiding class. For example any wedge permutations is in the grid class (but not the only grid class) with matrix -1 1 because every wedge permutation can be split horizontally such that the top part contains a decreasing subsequence and the bottom part contains an increasing subsequence. Another example is that a skew-merged permutation is in the grid class permutation with matrix -1 1 1 -1 . Some interesting points about the grid permutation are as follows:

• A more relevant example of an avoiding class that can be dene as a class of grid classes is that any separable permutation is in a grid class with a matrix of which each row and column have at most one element dierent from 0. This denition of separable permutation exhibits a class of matrix. A question that naturally arises is whether a class of matrices exists such that the P P M is solvable in polynomial time for the corresponding class of grid permutations. As a lead, we believe that whenever a pattern belong to the grid class with the matrix belonging in the class 1 ... 1 and 1 ... 1

of matrices, then PPM can be solved polynomially if the matrices have a xed size. Another class of matrices of xed size, that we believe can be solved polynomially, is dened as follow: for each element of the matrix dierent from 0, if its row contains another element dierent from 0 then its column is full of 0 and if its column contains another element dierent from 0 then its row is full of 0. The basics of an algorithm would be to . use an algorithm solving the case above and to combine it with a splitting strategy.

• The following question has been formulated in converse to the above lead: Does there exists a class of matrices such that the P P M over the associated grid classes is NP-complete? An example of such result is in the 321-avoiding permutations. Indeed, every 321-avoiding permutation is known to be split-table into two increasing subsequences, which means that every 321-avoiding permutations can be understood as a permutation in the grid class with matrices lled with 0 except for two diagonals south-west north-east which are lled with 1.

• Our rst intuition is that PPM can always be solved polynomially when the pattern is in a grid class of a given matrix. Indeed, an algorithm could try every possible grid in the text, and test whether each brick contains an increasing or a decreasing subsequence of sucient size, and try the compatibility between each brick. This would result in a polynomial algorithm in the size of the matrix, but does it yield a correct algorithm?

• Another interesting question is whether the PPM problem can be solved by a FTP algorithm by a value relevant to the size of the matrix of a grid class permutations. The algorithm of Marx and Guillemot [START_REF] Guillemot | Finding small patterns in permutations in linear time[END_REF] is exponential by the size of the pattern. In practice, the pattern can have up to 10000 elements, but can be in grid class with a small matrix.

Figure 3 . 1

 31 Figure 3.1 The plot of the permutation π = 52143.

  (a) The elements of π{: 4} are inside the dashed rectangle. (b) The elements of π{2 : 4} are inside the dashed rectangles.

Figure 3 . 2

 32 Figure 3.2 Omitting the element of π = 52143 by values.

Figure 3 .

 3 2 for an example. Omitting Elements by Position with Bounds. When we want to omit part of a permutation by the position of elements, we write π[i, j] to indicate that we are considering the elements that are on the right of the element π[i] and on the left of the element π[j]. In the same fashion, we write π[i :] when we are considering the elements that are on the right of the element π[i], (which is a short cut for π[i : n]) and π[: j] when we are considering the elements that are on the left of the element π[j], (which is a short cut for π[1 : j]). For example, in the permutation π = 52143, π[3 :] = 143, π[: 4] = 5214 and π[2 : 4] = 214. The disregard of elements by their positions can be understood by drawing two verticals lines and considering only the elements between the two lines. See Figure 3.3 for an example.

  .4 for an example.

  (a) The elements of π[2 : 4] are inside the dashed rectangle. (b) The elements of π[2 :] are inside the dashed rectangle.

Figure 3 . 3

 33 Figure 3.3 Omitting element of π = 52143 by positions.

Figure 3 . 4

 34 Figure 3.4 The rectangle ((2, 2), (4, 4)) of the permutation 52143.

Figure 3 . 5

 35 Figure 3.5 The permutation 391867452 and its reverse 254768193.

Figure 3 . 6 Figure 3 . 7 AFigure 3 . 8

 363738 Figure 3.6 The permutation 391867452 and its complement 719243658.

Figure 3 .

 3 Figure 3.10 The permutation 91645 and the lines to remove on the left and its reduction on the right.

⊕=Figure 3 .Figure 3 .

 33 Figure 3.11 The direct sum of permutations 312 and 3214: 312 ⊕ 3214 = 3126547.

Figure 3 .

 3 Figure 3.13 Two occurrences of 54321 in 391867452

  .14).

  (a) The BVP σ = 1234 2143 . (b) An occurrence of σ in 3216745.

  are in the forbidden areas.

Figure 3 . 14 Problem 25 .

 31425 Figure 3.14

  Case of the Problem

Figure 4 . 1

 41 Figure 4.1 The plots of the boxed mesh pattern 2143 and 2341.

Figure 4 . 2

 42 Figure 4.2 Results for the PPM problem when considering class for the pattern.

1 n

 1 and k refer to the size of the text and the pattern, respectively. 2 where T (resp. T ) is the tree representing π (resp. σ ), n T (resp. n T ) denotes the number of node of T (resp. T ) and l T (resp. l T ) denotes the number of leaves of T (resp. T ).

Figure 4 . 3

 43 Figure 4.3 Results for the PPM problem when considering the same class for the pattern and the text.

Figure 4 . 4 1 n

 441 Figure 4.4 Result for the PPM problem when considering dierent classes for the text and the pattern.

Figure 4 . 5

 45 Figure 4.5 Results for the PPM problem when considering dierent type of pattern.

  log log n) Section 7.5 1 n refers to the size of the permutation.

Figure 5 . 1

 51 Figure 5.1 Results about computing the longest subsequence of any permutation.

Figure 5 . 2

 52 Figure 5.2 Results about computing the longest common subsequence of two permutations.

Figure 5 . 3

 53 Figure 5.3 The 3-grid permutation.

Figure 5 . 4

 54 Figure 5.4 The 3-grid permutation and the occurrence of 132.

Figure 5 . 5

 55 Figure 5.5 The superpattern of the set of rie shue permutations of size 5: this permutations contains any rie shue permutation of size 5.

Result 1 Reference 1 k

 11 the minimum size is bounded by (k/e) 2 that contains every permutations of size k or its inverse of size k 2 /2 one of size (k + 1)k/2[45] refers to the size of the permutations.

Figure 5 . 6 2 )

 562 Figure 5.6 Results for the k-superpattern for set of permutations of size k.

Figure 5 . 7

 57 Figure 5.7 Results for the k-superpattern when restricting the set of permutations.

4 Figure 5 . 9

 459 Figure 5.9 The set of permutations obtained by the development of 2121.

Algorithm 1 :

 1 Data: A separable permutation π Result: A decomposition of π LRM axima = Compute all of the LRMax of π for each index ; RLM inima = Compute all of the RLMin of π for each index ;

Figure 6 . 1 A

 61 Figure 6.1 A separating tree T π for the permutation π = 342561 together with the corresponding sequences for each node.

Figure 6 . 2 AFigure 6 . 3

 6263 Figure 6.2 A separating tree and the compact separating tree of the permutation π = 453126987.

Figure 6 . 4

 64 Figure 6.4 The eect of removing a node from a tree.

Algorithm 7 :

 7 Data: The sequence of rectangles π = π 1 , . . . , π π of the largest decomposition of π Data: The sequence of rectangles σ 1 , . . . , σ σ of the largest decomposition of σ Result: The rightmost σ i such that σ 1 , . . . , σ i occurs in π initialising r with nothing ;

  is the bottommost element of σ and σ[i -1]σ[i] or σ[i] then we add the bottom left corner,• if σ[i] is the topmost element of σ and σ[i]σ[i + 1] or σ[i] then we add the bottom right corner, • if σ[i] is the leftmost element of σ and σ[i -1]σ[i] or σ[i]then we add the top left corner, and• if σ[i] is the leftmost element of σ and σ[i -1]σ[i] or σ[i]then we add the top right corner.

Figure 6 . 7 Figure 6 . 8

 6768 Figure 6.7 The rectangle given in input is split into a pair of rectangles such that the left rectangle is below and at the left of the right rectangle. Moreover they are next to each other to be optimal.

Figure 6 . 9

 69 Figure 6.9 The matching element of σ(v) and σ(v ) are consecutive in position if and only if σ(v) is matched to π[ι -1] and σ(v ) is matched to π[ι].

Figure 6 .

 6 Figure 6.10 If v occurs in the dotted rectangle then u occurs in the bold rectangle.

7. 1

 1 Structure of a Wedge Permutation 7.1.1 General Structure. Property 77. The rst element of any wedge permutations must be either the bottommost or the topmost element.Proof. Any other initial element would serve as a `2' in either a 231 or 213 with 1 and n as the `1' and `3' respectively.

Figure 7 . 1

 71 Figure 7.1 The wedge permutation 123984765. Every point that is on a northwest to south-east line represents a descent element and every point that is on a south-west to north-east line represents an ascent element.

Figure 7 . 2

 72 Figure 7.2 The wedge permutation 123984765. Every line represents a factor, every circled point represents the leftmost element of each factor, and LMEp represent the indexes of those elements.

Figure 7 . 3

 73 Figure 7.3 The topmost element of the sux starting at factor(i) is the leftmost element of factor(i -1) (represented by the gray dot). PM π σ (i, j) is the smallest value of the matching of the topmost element (the gray dot) in all the occurrences of the sux starting at LMEp(factor(i)) in π[j :].

  PM π σ (i, j) = min{∞}∪{π[j ] | b = PM π σ (i-1, j ) is not 0 and |f actor(i)| ≤ LIS π (j, j -1, b -1)} j <j • If factor(i) is an RLMax factor, then PM π σ (i, j) = max{0}∪{π[j ] | b = PM π σ (i-1, j ) is not ∞ and |f actor(i)| ≤ LDS π (j, j -1, b + 1)} j <j

  Moreover, σ[i :] has for bottom line the elements of σ[i :] in which m and m + 1 are underlined if and only if m and m + 1 are in σ[i :], and m and m + 1 are underlined in σ. For example, given σ = 1234 2143 , σ = 2143 and σ[2 :] = 234 143 . Below, we describe other structure properties of wedge permutations needed to solve the problem. Lemma 99. Let σ be a wedge permutation. • If σ[i] is an RLMin element and not the rightmost element, then σ[i] + 1 is to the right of σ[i]. • If σ[i] is an RLMax element and not the rightmost element, then σ[i] -1 is to the right of σ[i].

  For the rst point, by contradiction, let σ[α] = m and σ[β] = m + 1 and suppose that there exists α < γ < β, such that σ[γ] is an RLMin element. As we know that RLMin elements are strictly increasing. σ[α] < σ[γ] < σ[β], which contradicts the fact that σ[β] = σ[α] + 1. The base case nds an occurrence of the rightmost element of the pattern. If the rightmost element does not have any restriction on positions and values, then PM σ π (lb, ub, k, j) is true if and only if σ[k] is matched to π[j]. This is true if π[j] ∈ [lb, ub]. If σ[k] appears in σ then σ[k] must be matched to the rightmost element of π; thus j must be n. If σ[k] appears in σ then σ[k] must be matched to the leftmost element; thus j must be 1. If σ[k] appears in σ then σ[k] must be matched to the topmost element, which is n. If σ[k] appears in σ then σ[k] must be matched to the bottommost element, which is 1. If (σ[k] -1)σ[k] appears in σ, then the matching elements of σ[k] and σ[k] -1 must be consecutive in value, by recursion the value of the element matching σ[k] -1 plus 1 is recorded in lb. σ[k] must thus be matched to lb. If (σ[k]σ[k] + 1) appears in σ, then the element matching σ[k] and σ[k] + 1 must be consecutive in value, by recursion the value of the element matching σ[k] + 1 minus 1 is recorded in ub. σ[k] must thus be matched to ub.

1 .

 1 If σ[i]σ[i + 1] appears in σ, then the positions of the element matching σ[i] and σ[i + 1] must be consecutive. In other words, if σ[i] is matched to π[j] then σ[i + 1] must be matched to π[j + 1]. We ensure this restriction, by recursion, by requiring that the matching of σ[i + 1 :] starts at position j + Value Constraints. Three types of value constraints can be added by the overlined elements. • If σ[i] appears in σ (and thus σ[i] = 1) then the bottommost element of σ must be matched to the bottommost element of π. If σ[i] is an RLMin element, then: * Every problem PM σ π (lb, * , i, * ) is true only if σ[i] is matched to the element with a value lb (by recursion). Tt is thus enough to require that lb = 1. * The recursive calls for σ[1], . . ., σ[i -1] do not change the lower bound, as σ[i] is the leftmost RLMin element. Indeed the element 1 is the leftmost RLMin for any permutation. Finally, the recursive calls for RLMax elements do not change the lower bound. * The rst call of the problem has lb = 1 for parameter. As a result, PM σ π ( * , * , i, * ) returns true only if σ[i] is matched to 1. If σ[i] is an RLMax element, then i = k (σ[i] is the rightmost element). Every PM σ π ( * , * , i , * ) is thus a base case and true only if σ[i] is matched to lb. Moreover, recursive calls for RLMax elements do not change the lower bound. As such, PM σ π ( * , * , i, * ) returns true only if σ[i] is matched to lb = 1. • If σ[i] appears in σ (and thus σ[i] = k), then the topmost element of σ must be matched to the topmost element of π. If σ[i] is an RLMax element, then: * Every problem PM σ π ( * , ub, i, * ) is true only if σ[i] is matched to the element with value ub (by recursion). It is thus sucient to require that ub = n. * The recursive calls for σ[1], . . ., σ[i -1] do not change the upper bound, as σ[i] is the leftmost RLMax element. Indeed the element k is the leftmost RLMax for any permutation. Finally, the recursive calls for RLMin elements do not change the upper bound. * The rst call of the problem has ub = n for parameter. As such, PM σ π ( * , * , i, * ) returns true only if σ[i] is matched to n. If σ[i] is an RLMin element, then i = k (σ[i] is the rightmost element). Every PM σ π ( * , * , i , * ) is thus a base case and true if σ[i] is matched to ub. Moreover, recursive calls for RLMin elements do not change the upper bound. As a result, PM σ π ( * , * , i, * ) returns true only if σ[i]is matched to ub = n. • If σ[i]σ[i ] appears in σ, (which implies that σ[i ] = σ[i] + 1) and i < i(the case in which i > i can be dealt following the same idea), thenσ[i] is matched to π[j] and σ[i ] is matched to π[j] + 1.In the case whereσ[i] is an RLMax element is impossible, since σ[i ]is to the right of and aboveσ[i],in the σ[i] is an RLMin element, and σ[i ] is an RLMax element, thenremark that * i = k; indeed, if σ[i ] isnot the rightmost element, there would exist an element between σ[i] and σ[i ]. Every recursive call PM σ π (lb, * , i , * ) is thus solved as a base case. As such, PM σ π (lb, * , i , * ) is true only if σ[i ] is matched to the element lb. * The recursive calls for σ[i + 1], . . ., σ[i -1] do not change the lower bound. Indeed, σ[i] is the rightmost RLMin. As a result σ[i + 1], σ[i + 2], . . ., σ[i -1] are RLMax elements. Moreover, recursive calls for an RLMax do not change the lower bound. * PM σ π (lb, * , i, * ) sets the lb to π[j] + 1 and matches σ[i] to π[j]. As such, σ[i] is matched to π[j], and σ[i ] is matched to π[j] + 1. If σ[i] is an RLMin element and σ[i ] is a RLMin, element then: * Every recursive call PM σ π (lb, * , i , * ) is true only if σ[i ] is matched to the element with the value lb. * The recursive calls for σ[i + 1], . . ., σ[i -1] do not change the lower bound. Indeed, based on Lemma 100, σ[i + 1], . . ., σ[i -1] are RLMax elements. Finally, the recursive calls for RLMax elements do not change the lower bound. * PM σ π ( * , * , i, * ) sets lb to π[j] + 1 and matches σ[i] to π[j]. As such σ[i] is matched to π[j] and σ[i ] is matched to π[j] + 1.

Figure 8 . 1

 81 Figure 8.1 The permutation 149238756 is in the grid class permutations with matrix 0 -1 1 1

  Wedge permutationsO(max(kn 2 , n 2 log log n))-time Section 7.3 O(n 3 )-space 1 n and k refer to the size of the text and the pattern, respectively.

	Condition on σ	Complexity 1	Reference
	Permutation of size 4	O(n log n)-time	[6]
	21-avoiding 321-avoiding	O(n log log n)-time O(kn 4 √ k+12 )-time	[15] [33]
	Proper subclass of
	321-avoiding Proper subclass of	Polynomial algorithm	[35]
	(2143, 3412, 3142)-avoiding
	4312	Linear algorithm	[42]
	Separable permutations	O(kn 4 )-time O(log kn 3 )-space	Section 6.2

  The shue of 12 and 21 as a word, the elements are overlined and underlined to indicate which permutation the element comes from, and each leaf represent a set of permutations. Denition 41. Given σ and π, the shue of π and σ, (noted σ • π), is the set of permutations obtained by applying the shue to σ and π as words, where each word represents a set of permutations. The set represented is the set of every dierent permutation obtained by the following rule: Relabel each letter by increasing integers by replacing either the lowest element of σ or π not yet replaced until all elements are replaced.

			12 • 21
	1221	1221	2121	2112	2112
	Figure 5.8

An example is given in Figures 5.8 and 5.9. The denition of shue gives rise the following decision problem: Problem 42. Given the permutations σ 1 , σ 2 and π, the recognising shue for permutation problem asks whether

  6.1.2 Separable Permutations Seen as a Direct or Skew Sum Simple Decomposition in Sum Proposition 48. A separable permutation is either the trivial permutation of size 1 or obtained by a direct or skew sum of two separable permutations. Proof. We prove this claim by induction on the size of the permutation. A separable permutation π of size n can start by the topmost or bottommost element. In such cases, π can be written as 1 π[2 :] or 1 ⊕ π[2 :], respectively. If π does not start with the topmost or bottommost element, by hypothesis π[2

  append(π[i]) ; else while the last rectangle in the stack and R c form a contiguous set do pop R p from the stack ; if R c and R p form a contiguous set then if the elements of R p are above the elements of R p then

  It should be noted that σ[i] can be matched to π[j] because π[j] ∈ [lb, ub].As such, if π[j + 1 :] has an occurrence of σ[i + 1 :] with every element of the occurrence in [π[j] + 1, ub], if the condition on position between σ[i] and if σ[i + 1] (if any) is respected and the condition on value between σ[i] and σ[i] + 1 (if any) is respected, then π[j :] has an occurrence of σ[i :]. To decide the latter condition, by recursion, it is sucient to know if there exists , j < such that PM σ

	PM σ π (π[j] + 1, ub, i + 1, j + 1)	if σ[i]σ[i + 1]
		and (σ[i] -1)σ[i] or σ[i]
		appear in σ
		and π[j] = lb
	f alse	otherwise

 >j PM σ π (π[j] + 1, ub, i + 1, ) if σ[i] is not underlined and σ[i] is not overlined >j PM σ π (π[j] + 1, ub, i + 1, ) if σ[i] is not underlined and (σ[i] -1)σ[i] or σ[i] appears in σ and π[j] = lb PM σ π (π[j] + 1, ub, i + 1, j + 1) if σ[i]σ[i + 1]

appears in σ and σ[i] is not overlined π (π[j] + 1, ub, i + 1, ) is true. The rst case

Moreover, when the elements are the rst n integers, we rename the elements such that the elements are still read in their natural linear order, for comprehension purposes. In a plot, this corresponds to a reection on the x-axis. A simple algorithm that computes the complement of permutation of size n, is putting at position i the element n -i + 1. For example, the complement of the permutation 391867452 is 719243658. See Figure3.6.

in T σ contains at least half of the nodes of T σ . The same argument applies for subsequent maximal black subtrees in the forest T b .6.3 Both π and σ are Separable PermutationsIn this section, we focus on the case in which both the text and the pattern are separable permutations. Although our algorithm does not have better complexity in terms of time and space than the best algorithm so far, we contribute by providing an algorithm more specic to the separable permutations.

All the leaves of the compact separable trees have to be labelled 1. It should be noted that this does not modify the corresponding separable

Algorithm 5 presents the pseudo-code of an algorithm that constructs such a sequence, which can be used to decide whether σ occurs in π.

The algorithm in[START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF] is well suited for our case as it computes not only the longest increasing/decreasing subsequence between j and j but also for every k and k such that j < k < k < j .

This section focuses on a problem related to the PPM problem, continuing the work undertaken in[START_REF] Bouvel | Longest Common Separable Pattern between Permutations[END_REF] and in[START_REF] Neou | Pattern matching for separable permutations[END_REF].

Remerciements

and above depending of the sign) the rectangle of the right part. This gives us the following algorithm.

Algorithm 3:

Data: A permutation π Data: A separable permutation σ Result: Whether σ occurs in π if π is empty then return False ;

if σ = σ l ⊕ σ r then for every pair of rectangles (r l , r r ) of π such that r l is left and below r r do if σ l occurs in r l AND σ r occurs in r r then return True ;

else if σ = σ l σ r then for every pair of rectangles (r l , r r ) of π such that r l is left and above r r do if σ l occurs in r l AND σ r occurs in r r then return True ;

else if σ = 1 then return True ;

return False ;

The following remarks improve the current state of the algorithm or provide more insight for understanding the dierence with the algorithm of Ibarra (Algorithm s3) :

Remark 56. For practical reasons and to understand the improvement of Ibarra's algorithm, we need to delve deeper into the representation of the input. In particular, the algorithm does not receive a subsequence of π, but π and a rectangle.

Remark 57. One instance may be called multiple times. To avoid computing the same instance, the algorithm uses a dynamic programming strategy: Each time that it computes an instance, it remembers the value computed. Whenever it needs an instance, it rst checks whether this instance has been already computed.

Remark 58. Since σ is a separable permutation, we can assume that we are given a separating tree T σ for σ, or we construct it in linear time and space. Having a separating tree allows to decide whether σ = σ l ⊕ σ r or σ = σ l σ r in constant time.

Remark 59. To iterate over all of the pair rectangles (r l , r r ) such that r l is left and below r r , we only need for the top right corner of r l to be to the left and below the bottom left corner of r r . A similar remark applies to the pair of rectangles (r l , r r ) such that r l is left and above r r : We only need the bottom right corner of r l to be left and above the top left corner of r r .

Remark 60. We actually do not need to iterate over all of the pairs of rectangles that are compatible. Indeed, if a smaller rectangle r s is contained in a

Improved Version of Ibarra

In this section, we show that we can improve the algorithm of Ibarra to reduce the space consumption.

Proposition 62. The memory consumption of the algorithm of Ibarra can be reduced to O(n 3 log k).

Proof. It should rst be observed that to compute all of the instances in which the pattern is the subpermutation σ (i.e. P P M _Ibarra(π, * , * , * , σ) ), we only need all of the instances in which the pattern is the left operand of σ in the decomposition, (that is, P P M _Ibarra(π, * , * , * , σ l )) and all of the instances in which the pattern is the right operand of σ (that is, P P M _Ibarra(π, * , * , * , σ r )). As such, some entries in the dynamic programming array become Algorithm 5: Data: The sequence of rectangles π 1 , . . . , π π of the largest decomposition of π.

Data: The sequence of rectangles σ 1 , . . . , σ σ of the largest decomposition of σ.

Result: A sequence as describe above.

start with an empty ordered partition and an empty subsequence ; Initialise s with s = σ 1 , . It should be noted that during the loop, the current rectangle is decomposed into a skew sum. We consider three cases: p is empty, p contains one rectangle R σ or p contains several rectangles S. In the second case, both R and R σ are decomposed into skew sum, which means that we must decide whether a largest decomposition in skew sum occurs in another largest decomposition in skew sum, which is solved by the current algorithm, so this case is solved by a recursive call. In the third case, S represents largest decomposition in direct sum, which means that we must decide whether the largest decomposition in direct sum (S) occurs in a largest decomposition in skew sum (the current rectangle). We show how to solve this later.

As seen above, the algorithm computes a sequence. As such, if it yields a solution, then σ occurs in π. To show that our algorithm nds a solution if and only if σ occurs in π, we still need to prove that no solution exists if the algorithm does not nd a sequence. We prove the contraposition below.

Suppose that a sequence (π i , P i ) solution exists and that our algorithm does not compute a solution. We prove that this assertion is not possible. Suppose the rst dierence between a sequence solution and the sequence computed by the algorithm appears for the rectangle π i , that is that the set P i is not the same as in the solution. The set can be dierent in three ways: The computed set is empty, the computed set is contained in P i or the computed set contains P i . The rst case is not possible because it implies that nothing occurs in π i ; however, by hypothesis at least P i occurs in π i (because of the sequence solution). The second case implies that the algorithm does not compute the largest set of rectangles, which is also not possible. If the third case occurs, we can create a new solution that is closer to the sequence computed: As the set P i computed by the algorithm contains the set P i , we replace the pair (π i , P i ) with the pair (π i , P i ) in the sequence of solution, to create a new sequence (that is also a solution). As P i contains more rectangles than P i , in the next sets P j , we remove the rectangles that appear in P i but not in P i . We thus Base: If v is a leaf, then :

F alse otherwise A leaf occurs in ((i, lb), (j, ub)) if and only if the rectangle is not empty, which is what the rst condition tests. The next four conditions assure that the matched element is on an edge of ((i, lb), (j, ub)). For example, if σ(v)σ(v + 1) then the matched element must be on the right edge, and intuitively σ(v + 1) will be on the left edge of the "next" rectangle.

Step. Here i < j and lb < ub and we let v L and v R stand for the left and right children of v respectively. Suppose that σ(v) occurs in ((i, lb), (j, ub)), and that v is a positive node. As such, σ(v) = σ(v L )⊕σ(v R ); in other words, σ(v) forms a stair up of two rectangles as must the occurrence of σ(v). An occurrence of σ(v) is thus composed of a left rectangle that contains the occurrence of σ(v L ) and a right rectangle that contains the occurrence of σ(v R ).

To nd whether σ(v) occurs in ((i, lb), (j, ub)), we just have to nd whether such occurrence of σ(v L ) and σ(v R ) exist. We can do so by trying every pair of such rectangles. However, to reduce the number of pairs to test and control the position and value of the elements of the occurrence, we require that the left rectangle share the same bottom and left edges as the rectangle ((i, lb), (j, ub)). That is the left rectangle is ((i, lb), ( * , * )), the right rectangle shares the same top edge and the same right edge as rectangle ((i, lb), (j, ub)) It others words, the right rectangle is (( * , * ), (j, ub)) and the left rectangle is consecutive in x and y coordinates to the right rectangle. We hence try to nd occurrences of σ(v L ) and σ(v R ) in every pair of rectangles ((i, ι -1), (lb, b -1) and ((ι, j), (b, ub)) (see Figure 6.7). In notation, this give us the following:

The case in which v is a negative node can be deduced following the same idea:

If no conditions on positions or values exist, this algorithm solves the pattern matching problem: If σ = σ α ⊕ σ β , then every element of σ α is left of and below every element of σ β . Moreover, if occurrences of σ α and σ β exist such that [2 :] according to the induction hypothesis, it follows that t[2 :] is an occurrence of σ[2 :]. Moreover, as B(t) [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] = B(σ) [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF], t [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] and σ [START_REF] Ahal | On Complexity of the Subpattern Problem[END_REF] are both either the bottommost or the topmost elements of their respective sequences. Therefore, t is an occurrence of σ in π.

A greedy algorithm decides whether σ occurs in π. One needs to read both permutations from left to right stopping at the second to last element. If both elements are RLMax or RLMin, the element of π is added to the solution, and it goes to the next elements in both permutation; it otherwise goes to the next element in the text permutation. As soon as the iteration stops because σ contains no elements, there exists an occurrence; otherwise, no occurrence exists.

Moreover, according to Property 82, we do not need to compute the words B(σ) and B(π) before running the greedy algorithm. Deciding whether an element is RLMax or RLMin can be done locally. The computation can be done while the algorithm is being run, which thus yields an on-line algorithm.

Data: A wedge permutation π Data: A wedge permutation σ Result: An occurrence of σ in π, if any.

while i is smaller than the size of π AND j is smaller than the size of σ do if π[i] and σ[j] are both RLMax element then add σ[j] to S ;

if j is larger than the size of σ then add the rightmost element of σ to S ; return S ; else return that no solution exists ;

Only σ is a Wedge Permutation

This section focusses on the permutation pattern matching problem in cases in which only the pattern σ is a wedge permutation. We rst highlight some properties of the decomposition in factors of a wedge permutation.

Property 85. In a wedge permutation, a factor is either an increasing or a decreasing sequence of contiguous elements.

Proof. A factor is a sequence of RLMin or RLMax elements. It should be recalled that any sub-sequence of RLMin or RLMax forms an increasing or decreasing subsequence (see Property 79), especially for a factor. For the contiguous part, we focus on RLMin elements, as the same idea can applied to RLMax elements. Suppose that two consecutive RLMin elements π[i] and π[i + 1] are not contiguous. In that case, there exists an element π

] is an RLMin element there is no elements to its right below which are below it, π[j] is thus to the left of π

In other words, j < i < i + 1 and

] is an occurrence of 231, which is not possible, as π is a wedge permutation.

Property 86. A rectangle of π contains an occurrence of an RLMin (resp.

RLMax) factor if and only if it contains an increasing (resp. decreasing) subsequence that is of the same size as or larger than the size of the factor.

Proof. This is a direct consequence of Property 85

We provide a property of wedge permutations that allows us to decide whether a rectangle contains an occurrence of a wedge permutation.

Lemma 87. There exists an occurrence of a wedge permutation starting with a leftmost RLMin (resp. RLMax) factor if and only if there are two occurrences Remark 88. Lemma 87 is based on the fact that a wedge permutation is a separable permutation, which means that, any wedge permutation can be decomposed into a direct/skew sum. In particular, for each wedge permutation π there exists a decomposition π 1 ⊕ π 2 or π 1 π 2 in which π 1 is the leftmost factor and π 2 is the rest of the permutation. For example, for the permutation 123984765, which is split into factors as 123 -98 -4 -765, scan be written as 123 ⊕ 984765.

A Simple Algorithm

We show how to compute permutation pattern matching using Lemma 87. The algorithm given in the proof is not the best we can do with respect to time and space complexity, but it helps to clarify the better version described in the proof of Proposition 98.

Lemma 89. Let σ be a wedge permutation of size k and π a permutation of size n. It can be decided in polynomial time and space whether π contains an occurrence of σ.

Proof. We solve the problem of deciding whether a rectangle ((j, lb), (j , ub)) contains an occurrence of factor(i) . . . factor(i ). More formally,

T rue if and only if ((j, lb), (j , ub)) contains an occurrence of factor(i) . . . factor(1)

F alse Otherwise

Based on Lemma 87, we know that this corresponds to computing an occurrence of factor(i) in a rectangle R l and an occurrence of factor(i-1) . . . factor(1) in a rectangle R 2 such that R 1 is to the left of and below R 2 if factor(i) is an RLMin factor; and R 1 is to the left of and above R 2 if factor(i) is an RLMax factor. The strategy for doing so is to try every pair of rectangles that follows this condition and determine whether they contain the occurrences. It should be noted that, for the rectangle R 1 , we need to compute an occurrence for a unique factor, which we know how to solve as a result of Property 86. For the second R 2 , we have the same problem with a dierent instance. As the new instance has a smaller size than the original one, each instance becomes easier until we have to compute a trivial instance.

Algorithm 8:

Data: A permutation π and a rectangle ((j, lb), (j , ub) Data: A wedge permutations σ and its decomposition into factors To decide whether a rectangle contains an increasing or decreasing subsequence of sucient size, Algorithm 9 can compute the LIS or LDS of this rectangle. This can be done in polynomial time in number of elements of the rectangle, this number is bounded by the size of the text. Algorithm 9 thus run in polynomial time in the size of the text. Algorithm 8 have a rectangle as an input and iterate over every way of splitting this rectangle into two rectangles which are comparable. The number of splitting is polynomial bounded by the rectangle in input which is bounded by the size of the the text. Algorithm 8 thus run in polynomial time in the size of the text.

The following remarks reduce the complexity of Algorithm 8.

Remark 90. Remark 60 also applies here.

Remark 91. Deciding whether a rectangle contains a factor corresponds to nding its longest increasing or decreasing subsequence and comparing this subsequence's size with the factor's size. The best algorithm so far for computing the longest increasing/decreasing is provided by Bespamyatnikh and Segal in [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF]. It runs in O(n log log n) where n is the size of the permutation we want to compute.

Remark 92. Computing every solution of the longest increasing/decreasing subsequence before running the main algorithm oers two advantages:

1. We may want to nd an occurrence in a rectangle more than one time,

and computing the answer once is enough.

Proposition 101. Let σ be a bivincular wedge permutation pattern of size k and π be a permutation of size n. It can be decided in O(kn 4 ) time and O(kn 3 ) space if π contains an occurrence of σ.

Proof. Consider the following problem: Given a lower bound lb, an upper bound ub, a position i of σ and a position j of π, we want to know if there is an occurrence of σ[i :] in π[j :] with every element of the occurrence in [lb, ub] and starting at π[j]. In other words, we wish to determine if the rectangle with the bottom left corner (j, lb) and the top right corner (n, ub) contains an occurrence of σ[i :] starting at π[j]. More formally stated,

with every element of the occurrence in [lb, ub] and starting at π[j] and if

appears in σ then π contains an occurrence of the bivincular wedge permutation pattern σ if and only if

We show how to compute those values recursively. Informally, given that σ[i] is an RLMin element, nding an occurrence of σ[i :] in π[j :] requires us to nd a rectangle R in π such that R contains an occurrence of σ[i + 1 :] and R is to the right and above π[j]. Moreover

, then we require that π[j] and R be next to each other horizontally and that the occurrence in R starts at the left edge of R. In other words, R has j + 1 for its left edge.

) then we require that π[j] and R be next to each other vertically and that the minimal element in the occurrence is on the bottom edge of R. In other words, R has for its bottom edge π[j] + 1.

Note that the parameters lb, ub and j correspond to the occurrence of σ[i + 1 :] and are respectively, the bottom, the top and the left edges of the rectangle R.

The case in which σ[i] is an RLMax element can be dealt with symmetrically. More formally stated: BASE:

f alse otherwise corresponds to an occurrence without restrictions on position and on value.

It is enough to know if there exists > j such that PM σ π (π[j]+1, ub, i+1, ) is true. The second case asks for the matching of σ[i] -1 and σ[i] to be consecutive in value, but the matching of σ[i] -1 is lb -1; as such, we want π[j] = lb. As the third case asks for the matching of σ[i] and σ[i + 1] to be consecutive in positions, the matching of σ[i + 1] must be π[j + 1]. The fourth case is a union of the second and third cases.

appear in σ and π[j] = ub f alse otherwise

The same remark as in the previous case holds.

Some constraints do not appear when we compute PM σ π ( * , * , i, * ). In particular, in the case in which σ[i] is an RLMin, the conditions of σ[i -1]σ[i] or/and σ[i](σ[i] + 1) are not considered in the recursion. Moreover, σ[i -1]σ[i] is not considered because it is up to PM σ π ( * , * , i -1, * ) to ensure that the elements corresponding to elements at position i -1 and i in an occurrence are next to each other in position. In addition σ[i](σ[i] + 1) is not considered because σ[i] + 1 is to the right of σ[i] (see Lemma 99) and addressed during the calls of PM σ π ( * , * , i , * ) for some

does not appear in the conditions for the exact same reason, and

The procedure clearly returns true if π contains an occurrence of σ if constraints on position or value exist. We next discuss how the position and value constraints are taken into account so that the algorithm returns true if and only if π has an occurrence of σ.

Position Constraints. Three types of position constraints can be added by the underlined elements.

Given a set of permutations, the longest permutation that occurs in each permutation of the set. This problem is known to be NP-Hard for an arbitrary size of the set even when all of its permutations are separable (see [START_REF] Bouvel | Longest Common Separable Pattern between Permutations[END_REF]). We demonstrate how to compute the longest wedge permutation occurring in a set, although we do not hope that the problem is solvable in polynomial time if the size of the set is not xed. Indeed, the size of the set appears in the exponent in the complexity of the algorithm. We thus focus on cases in which sets have only one or two permutations.

For convenience, we say that a subsequence is a wedge subsequence if and only if the permutation it represents is a wedge permutation.

We start with the easiest case in which only one input permutation is at play. We need the sets of RLMax and RLMin elements:

Proposition 102. If s i is the LIS with the last element at position f in π and s d is the LDS with the last element at position f in π then s i ∪ s d is a longest wedge subsequence with the last element at position f in π.

Proof. Let us rst prove that we have a wedge subsequence. Indeed, s i is an increasing subsequence with values below or equal to π[f ], and s d is a decreasing subsequence with values above or equal to π[f ]; as such, s i ∪ s d is a wedge subsequence. Let us prove that this is a longest one. Let s be a wedge subsequence with its rightmost element at position f in π such that |s| > |s i ∪ s d |. It should rst be noted that A(s) is also an increasing subsequence with its rightmost element at position f in π and that D(s) is also a decreasing subsequence with its rightmost element at position f in π. Proof. Proposition 102 leads to an algorithm in which one computes the LIS and LDS ending at every possible position and then nds the maximum sum of the LIS and LDS. LIS and LDS can be computed in O(n log(log(n))) time and O(n) space (see [START_REF] Bespamyatnikh | Enumerating longest increasing subsequences and patience sorting[END_REF]); the maximums can then be found done in linear time.

We next consider a case in which the input is composed of two permutations.

Proposition 104. Given two permutations π 1 of size n 1 and π 2 of size n 2 , the longest common wedge subsequence can be computed in O(n 3 1 n 3 2 ) time and space. Proof. Consider the following problem that computes the longest wedge subsequence common to π 1 and π 2 : Given two permutations π 1 and π 2 , we dene LCS π1,lb1,ub1,π2,lb2,ub2,i1,i2 = max {|s| | s occurs π 1 [i 1 :] with every element of the occurrence in [lb

otherwise

The solution to this problem relies on the fact that the longest wedge subsequence is found by considering the problem with π 1 [i 1 :] and π 2 [i 2 + 1 :] or π 1 [i 1 + 1 :] and π 2 [i 2 :] or by matching π 1 [i 1 ] and π 2 [i 2 ] and adding to the solution the LCS for π 1 [i 1 + 1 :] and π 2 [i 2 + 1 :] which is compatible, meaning that, if we consider the current elements to correspond to an RLMin (resp. RLMax) element in the longest wedge subsequence, then we consider only the solution with elements above (below) π