On intrinsically ambiguous rational relations

• Rodrigo de Souza UFRPE

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

Abstract

The family of rational relations, or the relations between words which can be realised by transducers (automata with inputs and outputs) is considered. Not every rational relation can be realised by an unambiguous transducer. Our main contribution is a characterisation of the intrinsically ambiguous k-valued rational relations based on the concept of lag between successful computations. We also show that it is undecidable whether the union of two rational functions is an intrinsically ambiguous relation. Finally, we show that the unambiguous k-valued relations are precisely the sums of k pairwise disjoint rational functions. Our proofs are built on structural constructions with automata based on the concept of covering of automata.

References

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.