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 AsGet 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
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.
Keywords
- Rational relation
- $k$-valued transducer
- unambiguous transducer
- covering of automata
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads