Correspondência de padrões de permutação em strings

Em termos gerais, a correspondência de padrões de permutação lida com problemas do seguinte tipo:

Dadas as permutações em e em , com , contém uma subsequência de comprimento cujos elementos são ordenados de acordo com ?$\pi$$S_n$$\sigma$$S_m$$m\leq n$$\pi$ $\tau$$m$$\sigma$

Por exemplo, se e , a subsequência corresponde a . Como você pode ver, não estamos procurando aqui uma correspondência exata, mas algo que "se pareça" com o padrão especificado.$\pi=\langle 3\ 1\ 5\ 4\ 2\ 8\ 6\ 7\rangle$$\sigma=\langle 2\ 1\ 3\rangle$$3\ 1\ 4$$\sigma$

Alguém sabe se o trabalho foi realizado para estender os problemas de correspondência de padrões de permutação às seqüências de caracteres? Infelizmente, o Google não ajudou, pois o conhecido problema de correspondência de padrões nas strings não tem nada a ver com isso.

Finalmente, consegui descobrir uma boa pesquisa de Kitaev e Mansour , que fornece indicações para a literatura relacionada ao padrão de permutação correspondente às permutações e palavras "usuais" / assinadas / coloridas.

Baars, Löh e Swierstra implementaram Analisadores de Permutação para Haskell (Journal of Functional Programming / Volume 14 / Edição 06, pp 635 - 646). Eles podem ser usados ​​para especificar a permutação de uma coleção de analisadores. Se cada um desses analisadores for um analisador opcional para um único caractere (ou seja, corresponde ao caractere ou a nada), você terá os ingredientes que procura. Acredito que a biblioteca deles esteja disponível no GHC.

Você deve começar com Revital Eres, Gad M. Landau, Laxmi Parida: descoberta de padrões de permutação em biosequências . Journal of Computational Biology 11 (6): 1050-1060 (2004).