Document Open Access Logo

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

Authors Mikołaj Bojańczyk, Janusz Schmude

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.19.pdf
  • Filesize: 1.55 MB
  • 14 pages

Document Identifiers

Author Details

Mikołaj Bojańczyk
  • Institute of Informatics, University of Warsaw, Poland
Janusz Schmude
  • Institute of Informatics, University of Warsaw, Poland

Funding

Supported by ERC Consolidator Grant LIPA, agreement no. 683080.

Cite As Get BibTex

Mikołaj Bojańczyk and Janusz Schmude. Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.19

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Formal languages and automata theory
Keywords
  • equivalence for mso transductions
  • bounded treewidth
  • Hilbert basis theorem

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Rajeev Alur and Loris D'Antoni. Streaming Tree Transducers. J. ACM, 64(5):31:1-31:55, August 2017. Google Scholar
  2. Rajeev Alur, Loris D'Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan. Regular functions and cost register automata. In Logic in Computer Science, LICS, New Orleans, USA, pages 13-22. IEEE Computer Society, 2013. Google Scholar
  3. Stefan Arnborg, Bruno Courcelle, Andrzej Proskurowski, and Detlef Seese. An algebraic theory of graph reduction. J. ACM, 40:1134-1164, January 1993. Google Scholar
  4. Stefan Arnborg, Jens Lagergren, and Detlef Seese. Problems easy for tree-decomposable graphs extended abstract. In Timo Lepistö and Arto Salomaa, editors, Automata, Languages and Programming, pages 38-51, Berlin, Heidelberg, 1988. Springer Berlin Heidelberg. Google Scholar
  5. Roderick Bloem and Joost Engelfriet. A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute Grammars. Journal of Computer and System Sciences, 61(1):1-50, 2000. Google Scholar
  6. Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude. Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method". In Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 48:1-48:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  7. Mikołaj Bojańczyk. The Hilbert method for transducer equivalence. SIGLOG News, 6(1):5-17, 2019. Google Scholar
  8. Mikołaj Bojańczyk and Michal Pilipczuk. Optimizing Tree Decompositions in MSO. In Heribert Vollmer and Brigitte Vallée, editors, Symposium on Theoretical Aspects of Computer Science, STACS, Hannover, Germany, volume 66 of LIPIcs, pages 15:1-15:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  9. Bruno Courcelle. The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Information and Computation, 85(1):12-75, March 1990. Google Scholar
  10. Bruno Courcelle. The monadic second-order logic of graphs v: on closing the gap between definability and recognizability. Theoretical Computer Science, 80(2):153-202, 1991. Google Scholar
  11. Bruno Courcelle. The monadic second order logic of graphs vi: on several representations of graphs by relational structures. Discrete Applied Mathematics, 54(2):117-149, 1994. Google Scholar
  12. Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic - A Language-Theoretic Approach, volume 138 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2012. Google Scholar
  13. Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets Weisfeiler and Leman. In International Colloquium on Automata, Languages, and Programming, ICALP, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1-40:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  14. Reinhard Diestel. Graph theory (Electronic Edition), volume 173 of Graduate texts in mathematics. Springer-Verlag, 2006. Google Scholar
  15. Joost Engelfriet. A characterization of context-free nce graph languages by monadic second-order logic on trees. In Hartmut Ehrig, Hans-Jörg Kreowski, and Grzegorz Rozenberg, editors, Graph Grammars and Their Application to Computer Science, pages 311-327, Berlin, Heidelberg, 1991. Springer Berlin Heidelberg. Google Scholar
  16. Joost Engelfriet and Hendrik Jan Hoogeboom. MSO Definable String Transductions and Two-way Finite-state Transducers. ACM Trans. Comput. Logic, 2(2):216-254, 2001. Google Scholar
  17. Eitan M. Gurari. The Equivalence Problem for Deterministic Two-Way Sequential Transducers is Decidable. SIAM J. Comput., 11(3):448-452, 1982. Google Scholar
  18. Donald E. Knuth. Semantics of context-free languages. Mathematical systems theory, 2(2):127-145, 1968. Google Scholar
  19. László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321-328, 1967. Google Scholar
  20. Jacques Sakarovitch. Elements of automata theory. Cambridge University Press, 2009. Google Scholar
  21. Allen J Schwenk. Almost all trees are cospectral, new directions in the theory of graphs (proc. third ann arbor conf., univ. michigan, ann arbor, mich., 1971), 1973. Google Scholar
  22. Detlef Seese. The structure of the models of decidable monadic theories of graphs. Annals of pure and applied logic, 53(2):169-195, 1991. Google Scholar
  23. Helmut Seidl, Sebastian Maneth, and Gregor Kemper. Equivalence of deterministic top-down tree-to-string transducers is decidable. J. ACM, 65(4), April 2018. Google Scholar
  24. J. W. Thatcher and J. B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Mathematical systems theory, 2(1):57-81, March 1968. Google Scholar
  25. Wolfgang Thomas. Languages, automata, and logic. In Handbook of formal languages, Vol. 3, pages 389-455. Springer, Berlin, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact