License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1324
URN: urn:nbn:de:0030-drops-13245
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1324/
Go to the corresponding LIPIcs Volume Portal

Sakarovitch, Jacques ; de Souza, Rodrigo

On the decomposition of k-valued rational relations

pdf-format:
22011.SakarovitchJacques.Paper.1324.pdf (0.2 MB)

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.

BibTeX - Entry

@InProceedings{sakarovitch_et_al:LIPIcs:2008:1324,
  author =	{Jacques Sakarovitch and Rodrigo de Souza},
  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 =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/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}
}

Keywords: Rational relation, $k$-valued transducer, unambiguous transducer, covering of automata
Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI