Novos Algoritmos para a Compressão de Sequências Parcialmente Comutativas

Neste artigo, são apresentados dois novos métodos para a compressão de sequências definidas em alfabetos com ordem parcial. Os métodos utilizam conceitos dos monoides de comutatividade e da forma normal de Foata associada com o LZ78 para proporcionar maiores taxas de compressão. São obtidos alguns limitantes para a complexidade de sequências. Os métodos propostos apresentam ganho na compressão de sequências nos exemplos considerados quando comparados o Sequitur comutativo e com o LZ78.