License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.125
URN: urn:nbn:de:0030-drops-62605
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6260/
Go to the corresponding LIPIcs Volume Portal

Filiot, Emmanuel ; Jecker, Ismaël ; Löding, Christof ; Winter, Sarah

On Equivalence and Uniformisation Problems for Finite Transducers

pdf-format:
LIPIcs-ICALP-2016-125.pdf (0.5 MB)

Abstract

Transductions are binary relations of finite words. For rational transductions, i.e., transductions defined by finite transducers, the inclusion, equivalence and sequential uniformisation problems are known to be undecidable. In this paper, we investigate stronger variants of inclusion, equivalence and sequential uniformisation, based on a general notion of transducer resynchronisation, and show their decidability. We also investigate the classes of finite-valued rational transductions and deterministic rational transductions, which are known to have a decidable equivalence problem. We show that sequential uniformisation is also decidable for them.

BibTeX - Entry

@InProceedings{filiot_et_al:LIPIcs:2016:6260,
  author =	{Emmanuel Filiot and Isma{\"e}l Jecker and Christof L{\"o}ding and Sarah Winter},
  title =	{{On Equivalence and Uniformisation Problems for Finite Transducers}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{125:1--125:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6260},
  URN =		{urn:nbn:de:0030-drops-62605},
  doi =		{10.4230/LIPIcs.ICALP.2016.125},
  annote =	{Keywords: Transducers, Equivalence, Uniformisation}
}

Keywords: Transducers, Equivalence, Uniformisation
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

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