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.FSTTCS.2018.48
URN: urn:nbn:de:0030-drops-99479
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9947/
Go to the corresponding LIPIcs Volume Portal

Boiret, Adrien ; Piórkowski, Radoslaw ; Schmude, Janusz

Reducing Transducer Equivalence to Register Automata Problems Solved by "Hilbert Method"

pdf-format:
LIPIcs-FSTTCS-2018-48.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{boiret_et_al:LIPIcs:2018:9947,
  author =	{Adrien Boiret and Radoslaw Pi{\'o}rkowski and Janusz Schmude},
  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 =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9947},
  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}
}

Keywords: formal language, Hilbert's basis theorem, transducers, register automata, equivalence problem, unordered trees, MSO transformations
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI