2026-07-22T06:50:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1324 2024-03-06T10:33:02Z ddc:004 open_access

On the decomposition of k-valued rational relations Sakarovitch, Jacques de Souza, Rodrigo Rational relation $k$-valued transducer unambiguous transducer covering of automata We give a new, and hopefully more easily understandable, structural proof of the decomposition of a $k$-valued transducer into $k$ unambiguous functional ones, a result established by A. Weber in 1996. Our construction is based on a lexicographic ordering of computations of automata and on two coverings that can be build by means of this ordering. The complexity of the construction, measured as the number of states of the transducers involved in the decomposition, improves the original one by one exponential. Moreover, this method allows further generalisation that solves the problem of decomposition of rational relations with bounded length-degree, which was left open in Weber's paper. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jacques Sakarovitch and Rodrigo de Souza 2008 Is Part Of LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2008.1324 urn:nbn:de:0030-drops-13245 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1324 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode