DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2008.1324

On the decomposition of k-valued rational relations

Authors: Jacques Sakarovitch and Rodrigo de Souza

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{sakarovitch_et_al:LIPIcs.STACS.2008.1324,
  author =	{Sakarovitch, Jacques and de Souza, Rodrigo},
  title =	{{On the decomposition of k-valued rational relations}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{621--632},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1324},
  URN =		{urn:nbn:de:0030-drops-13245},
  doi =		{10.4230/LIPIcs.STACS.2008.1324},
  annote =	{Keywords: Rational relation, \$k\$-valued transducer, unambiguous transducer, covering of automata}
}

Search Results

Documents authored by de Souza, Rodrigo

On the decomposition of k-valued rational relations

Abstract

Cite as

Thanks for your feedback!

Could not send message