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.FSTTCS.2018.22
URN: urn:nbn:de:0030-drops-99213
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9921/
Go to the corresponding LIPIcs Volume Portal

Bose, Sougata ; Muscholl, Anca ; Penelle, Vincent ; Puppis, Gabriele

Origin-Equivalence of Two-Way Word Transducers Is in PSPACE

pdf-format:
LIPIcs-FSTTCS-2018-22.pdf (0.5 MB)

Abstract

We consider equivalence and containment problems for word transductions. These problems are known to be undecidable when the transductions are relations between words realized by non-deterministic transducers, and become decidable when restricting to functions from words to words. Here we prove that decidability can be equally recovered the origin semantics, that was introduced by Bojanczyk in 2014. We prove that the equivalence and containment problems for two-way word transducers in the origin semantics are PSPACE-complete. We also consider a variant of the containment problem where two-way transducers are compared under the origin semantics, but in a more relaxed way, by allowing distortions of the origins. The possible distortions are described by means of a resynchronization relation. We propose MSO-definable resynchronizers and show that they preserve the decidability of the containment problem under resynchronizations.
{}

BibTeX - Entry

@InProceedings{bose_et_al:LIPIcs:2018:9921,
  author =	{Sougata Bose and Anca Muscholl and Vincent Penelle and Gabriele Puppis},
  title =	{{Origin-Equivalence of Two-Way Word Transducers Is in PSPACE}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9921},
  URN =		{urn:nbn:de:0030-drops-99213},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.22},
  annote =	{Keywords: Transducers, origin semantics, equivalence}
}

Keywords: Transducers, origin semantics, equivalence
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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