O problema da Satisfazibilidade Probabilística, PSAT, apesar da sua flexibilidade, torna exponencialmente complexa a modelagem de variáveis estatisticamente independentes. Esta tese busca desenvolver algoritmos e propostas de relaxamento para permitir o tratamento eficiente de independência parcial pelo PSAT. Apresentamos uma aplicação do PSAT ao problema da etiquetagem morfossintática que serve tanto de motivação como de demonstração dos conceitos apresentados.

The Probabilistic Satisfiability Problem, PSAT, despite its flexibility, makes it exponentially complicated to model statistically independent variables. This thesis develops algorithms and relaxation proposals that allow an efficient treatment of partial independence with PSAT. We also present an application of PSAT on the Part-of-speech tagging problem to serve both as motivation and showcase of the presented concepts.