2026-08-11T00:17:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12752 2024-03-06T10:50:35Z ddc:004 open_access

Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers Bojańczyk, Mikołaj Schmude, Janusz equivalence for mso transductions bounded treewidth Hilbert basis theorem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mikołaj Bojańczyk and Janusz Schmude 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.19 urn:nbn:de:0030-drops-127529 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.19 eng https://creativecommons.org/licenses/by/3.0/legalcode