Grafos de contextos de sistemas dinâmicos de memória infinita

Abstract

A teoria de sistemas dinâmicos simbólicos, que explora as propriedades de sequências com restrições, é aplicada em problemas nas áreas de comunicação digital e armazenamento de dados. Estes sistemas são especificados por um conjunto mínimo de sequências proibidas O, ou alternativamente, por um grafo direcionado rotulado, denominado de grafo de contextos. O contexto à direita de uma palavra w de um sistema dinâmico simbólico é o conjunto de todas as palavras que podem seguir w. Neste trabalho, emprega-se o conceito de conjunto de restrições de uma palavra que unicamente caracteriza o seu contexto à direita para a classe dos sistemas dinâmicos simbólicos periódicos (PFT, periodic shift of finite type) para estender o algoritmo de SFT, fundamentado no conceito de conjunto de restrições, para a construção do grafo de contextos para esta classe. Conjugando conceitos da teoria de dinâmica simbólica e da teoria dos autômatos, definimos um conjunto finito de palavras, denominado de conjunto suficiente de classes de representantes W, que gera todos os possíveis contextos à direita, para sistemas em que o conjunto O é infinito, denominados de sistemas dinâmicos simbólicos de memória infinita (SSS, strict sofic shift). Utilizando a cardinalidade de W determinamos um limitante para o número de elementos de um conjunto necessário e suficiente de classes de representantes de contextos de um SSS. Por fim, usando um procedimento sistemático para a partição deste conjunto, propomos um novo algoritmo para a construção do grafo de contextos para a classe de SSS, construção esta que é um problema em aberto na literatura.