Algoritmos para Geração de Classes de Extensões de Conjuntos Parcialmente Ordenados

Dado um conjunto finito E, uma ordenação parcial P em E é uma relação binária reflexiva, anti-simétrica e transitiva. Uma extensão de P é uma ordenação parcial Q em E tal que P é um subconjunto de Q. Consideramos epsilon(P) o conjunto de extensões de uma ordenação parcial P. Neste trabalho, estudamos caracterizações do conjunto de extensões de uma ordenação parcial P pertencentes a determinadas classes de ordenações, assim como métodos de geração de tais extensões. As classes de extensões estudadas incluem ordenações arbóreas, ordenações fracas, ordenações intervalares e semi-ordens. São apresentados métodos de geração de tais classes de extensões, baseados em uma caracterização de epsilon(P) --- utilizando o conceito de acréscimo lexicográfico de P. Em particular, é apresentado um método de geração de extensões intervalares de uma ordenação parcial P em tempo O(n^2) por extensão, assim como um método de geração de extensões semi-ordens de P em tempo O(n^3) por extensão.