Um modelo parcial de formação das classes de reversibilidade em autômatos celulares elementares

Abstract

O custoso processo de determinar computacionalmente o padrão de pré-imagens de regras de autômatos celulares permite particioná-las em diferentes nı́veis de reversibilidade. Visando simplificá-lo, apresentamos uma operação alternativa, definida diretamente das transições de estado, e a avaliamos no espaço elementar. Das 45 classes prováveis, 3 sofreram particionamento adicional, e a análise dos grafos de De Bruijn associados evidenciou importantes aspectos conceituais envolvidos.