LIPIcs.STACS.2008.1324.pdf
- Filesize: 208 kB
- 12 pages
Document
On the decomposition of k-valued rational relations
Authors
-
Part of:
Volume:
25th International Symposium on Theoretical Aspects of Computer Science (STACS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Theoretical Aspects of Computer Science (STACS) - License:
Creative Commons Attribution-NoDerivs 3.0 Unported license
- Publication Date: 2008-02-06
Cite As Get BibTex
Jacques Sakarovitch and Rodrigo de Souza. On the decomposition of k-valued rational relations. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 621-632, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.STACS.2008.1324
Abstract
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.
Subject Classification
Keywords
- Rational relation
- $k$-valued transducer
- unambiguous transducer
- covering of automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads