Sobre as relações racionais intrinsicamente ambíguas

• Rodrigo de Souza UFRPE

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 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.

Referências

Colcombet, T. (2015). Unambiguity in automata theory. In Proceedings of Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, volume 9118 of Lecture Notes in Computer Science, pages 3–18. Springer-Verlag.

de Souza, R. (2008). Approche structurelle des transducteurs de norme bornée. PhD thesis, TELECOM ParisTech.

Eilenberg, S. (1974). Automata, Languages, and Machines. Academic Press, Inc.

Sakarovitch, J. (1998). A construction on finite automata that has remained hidden. Theoretical Computer Science, 204(1-2):205–231.

Sakarovitch, J. (2009). Elements of Automata Theory. Cambridge University Press.

Sakarovitch, J. and de Souza, R. (2010). Lexicographic decomposition of k-valued transducers. Theory of Computing Systems, 47(3):758–785.