MO640 - Exercícios - Sobre a aula de 2006-05-24

Em seu artigo "A very elementery presentation of the Hannenhalli-Pevzner theory", a Dra. Anne Bergeron define o conceito de framed interval, que serve de ponto de partida para a definição de obstáculo, apenas em permutações reduzidas. Sugira uma definição para framed interval que sirva para qualquer permutação sem pares orientados, seja ela reduzida ou não. Em sua definição, os framed intervals minimais são exatamente os obstáculos? E as operações de corte e junção de obstáculos, conforme definidas por Bergeron, continuam a ter as propriedades que tinham (ou seja, permutações com apenas um obstáculo seriam resolvidas por apenas um corte, além das reversões orientadas; e permutações com apenas dois obstáculos seriam resolvidas com apenas uma junção, além das reversões orientadas).
Tente estender o conceito de framed interval para permutações gerais, incluindo aquelas que possuem pares orientados. Quais são as dificuldades que aparecem?