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.MFCS.2020.19
URN: urn:nbn:de:0030-drops-127529
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12752/
Go to the corresponding LIPIcs Volume Portal


Bojańczyk, Mikołaj ; Schmude, Janusz

Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers

pdf-format:
LIPIcs-MFCS-2020-19.pdf (2 MB)


Abstract

We study the following decision problem: given two mso transductions that input and output graphs of bounded treewidth, decide if they are equivalent, i.e. isomorphic inputs give isomorphic outputs. We do not know how to decide it, but we propose an approach that uses automata manipulating elements of a ring extended with division. The approach works for a variant of the problem, where isomorphism on output graphs is replaced by a relaxation of isomorphism.

BibTeX - Entry

@InProceedings{bojaczyk_et_al:LIPIcs:2020:12752,
  author =	{Miko{\l}aj Bojańczyk and Janusz Schmude},
  title =	{{Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12752},
  URN =		{urn:nbn:de:0030-drops-127529},
  doi =		{10.4230/LIPIcs.MFCS.2020.19},
  annote =	{Keywords: equivalence for mso transductions, bounded treewidth, Hilbert basis theorem}
}

Keywords: equivalence for mso transductions, bounded treewidth, Hilbert basis theorem
Collection: 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
Issue Date: 2020
Date of publication: 18.08.2020


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