Some remarks on deciding equivalence for graph-to-graph transducers

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 if this problem is decidable, but we propose an approach to deciding the problem which uses algebra. We show how the approach can be successful for a variant of the problem, where instead of isomorphism on output graphs, we consider certain relaxation of isomorphism. Our solution uses a variant of polynomial transducers, extended with a division operation. This is joint work with Mikołaj Bojańczyk.

Authors

• Janusz Schmude

Keywords

No keywords are indexed for this paper.