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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12752/
Bojańczyk, Mikołaj ;
Schmude, Janusz
Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers
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 |
