Search Results

Documents authored by Schmude, Janusz

Document
DOI: 10.4230/LIPIcs.MFCS.2020.19
Some Remarks on Deciding Equivalence for Graph-To-Graph Transducers

Authors: Mikołaj Bojańczyk and Janusz Schmude

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{bojanczyk_et_al:LIPIcs.MFCS.2020.19,
  author =	{Boja\'{n}czyk, Miko{\l}aj and Schmude, Janusz},
  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 =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.19},
  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}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.48
Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"

Authors: Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
In the past decades, classical results from algebra, including Hilbert's Basis Theorem, had various applications in formal languages, including a proof of the Ehrenfeucht Conjecture, decidability of HDT0L sequence equivalence, and decidability of the equivalence problem for functional tree-to-string transducers. In this paper, we study the scope of the algebraic methods mentioned above, particularily as applied to the functionality problem for register automata, and equivalence for functional register automata. We provide two results, one positive, one negative. The positive result is that functionality and equivalence are decidable for MSO transformations on unordered forests. The negative result comes from a try to extend this method to decide functionality and equivalence on macro tree transducers. We reduce macro tree transducers equivalence to an equivalence problem for some class of register automata naturally relevant to our method. We then prove this latter problem to be undecidable.
Cite as

Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude. Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method". In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{boiret_et_al:LIPIcs.FSTTCS.2018.48,
  author =	{Boiret, Adrien and Pi\'{o}rkowski, Radoslaw and Schmude, Janusz},
  title =	{{Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.48},
  URN =		{urn:nbn:de:0030-drops-99479},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.48},
  annote =	{Keywords: formal language, Hilbert's basis theorem, transducers, register automata, equivalence problem, unordered trees, MSO transformations}
}
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