Sobre as relações racionais intrinsicamente ambíguas

• Rodrigo de Souza

DOI: https://doi.org/10.5753/etc.2017.3207

Resumo

A família das relações racionais, ou relações entre palavras que podem ser realizadas por transdutores (autõmatos com entrada e sáıda) é considerada. Nem toda relação racional pode ser realizada por um transdutor nãoambíguo. Nossa principal contribuição é uma caracterização das relações kvaloradas intrinsicamente ambíguas baseada no conceito de deslocamento entre passeios. Também apresentamos uma prova simples de que é indecidível se a união de duas funções racionais é uma relação intrinsicamente ambígua. Finalmente, mostramos que as relações k-valoradas não-ambíguas são precisamente somas de k funções racionais duas a duas disjuntas. Nossas provas consistem de construções estruturais baseadas no conceito de revestimento de autõmatos.