Sobre as relações racionais intrinsicamente ambíguas - de Souza, Rodrigo (Anais do Encontro de Teoria da Computação (ETC), 2017)
A família das relações racionais, ou relações entre palavras que podem ser realizadas por transdutores (autômatos com entrada e saída) é considerada. Nem toda relação racional pode ser realizada por um transdutor não ambíguo. Nossa principal contribuição é uma caracterização das relações k-valoradas 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.