On the decomposition of k-valued rational relations

Authors Jacques Sakarovitch, Rodrigo de Souza



PDF
Thumbnail PDF

File

LIPIcs.STACS.2008.1324.pdf
  • Filesize: 208 kB
  • 12 pages

Document Identifiers

Author Details

Jacques Sakarovitch
Rodrigo de Souza

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

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)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail