Permutation pattern matching

Abstract : This thesis focuses on permutation pattern matching problem, which askswhether a pattern occurs in a text where both the pattern and text are permutations.In other words, we seek to determine whether there exist elements ofthe text such that they are sorted and appear in the same order as the elementsof the pattern. The problem is NP-complete. This thesis examines particularcases of the problem that are polynomial-time solvable.For this purpose, we study the problem by giving constraints on the permutationstext and/or pattern. In particular, the cases in which the text and/orpattern are permutations in which the patterns 2413 and 3142 do not occur(also known as separable permutations) and in which the text and/or patternare permutations in which the patterns 213 and 231 do not occur (also known aswedge permutations) are also considered. Some problems related to the patternmatching and the permutation pattern matching with bivincular pattern arealso studied.
Document type :
Theses
Complete list of metadatas

Cited literature [55 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/tel-01866721
Contributor : Abes Star <>
Submitted on : Monday, September 3, 2018 - 3:45:41 PM
Last modification on : Tuesday, March 19, 2019 - 11:58:18 PM
Long-term archiving on : Tuesday, December 4, 2018 - 5:51:22 PM

File

TH2017PESC1239.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-01866721, version 1

Collections

Citation

Both Emerite Neou. Permutation pattern matching. Document and Text Processing. Université Paris-Est; Université de Vérone (Italie), 2017. English. ⟨NNT : 2017PESC1239⟩. ⟨tel-01866721⟩

Share

Metrics

Record views

143

Files downloads

217