Document Open Access Logo

Decision Problems for Origin-Close Top-Down Tree Transducers

Author Sarah Winter

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2021.90.pdf
  • Filesize: 0.77 MB
  • 16 pages

Document Identifiers

Author Details

Sarah Winter
  • Université libre de Bruxelles, Brussels, Belgium

Funding

This research was supported by the DFG grant LO 1174/3.

Acknowledgements

The author wants to thank Emmanuel Filiot for valuable feedback on the presentation.

Cite As Get BibTex

Sarah Winter. Decision Problems for Origin-Close Top-Down Tree Transducers. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 90:1-90:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.MFCS.2021.90

Abstract

Tree transductions are binary relations of finite trees. For tree transductions defined by non-deterministic top-down tree transducers, inclusion, equivalence and synthesis problems are known to be undecidable. Adding origin semantics to tree transductions, i.e., tagging each output node with the input node it originates from, is a known way to recover decidability for inclusion and equivalence. The origin semantics is rather rigid, in this work, we introduce a similarity measure for transducers with origin semantics and show that we can decide inclusion, equivalence and synthesis problems for origin-close non-deterministic top-down tree transducers.

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
  • Theory of computation → Transducers
Keywords
  • tree tranducers
  • equivalence
  • uniformization
  • synthesis
  • origin semantics

Metrics

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

Related Versions

References

  1. Mikolaj Bojanczyk. Transducers with origin information. In ICALP (2), volume 8573 of Lecture Notes in Computer Science, pages 26-37. Springer, 2014. Google Scholar
  2. Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, and Vincent Penelle. Which classes of origin graphs are generated by transducers. In ICALP, volume 80 of LIPIcs, pages 114:1-114:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  3. Sougata Bose, Shankara Narayanan Krishna, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. On synthesis of resynchronizers for transducers. In MFCS, volume 138 of LIPIcs, pages 69:1-69:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  4. Sougata Bose, Anca Muscholl, Vincent Penelle, and Gabriele Puppis. Origin-equivalence of two-way word transducers is in PSPACE. In FSTTCS, volume 122 of LIPIcs, pages 22:1-22:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  5. Fabienne Braune, Nina Seemann, Daniel Quernheim, and Andreas Maletti. Shallow local multi-bottom-up tree transducers in statistical machine translation. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 811-821, 2013. Google Scholar
  6. J. Richard Büchi and Lawrence H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295-311, 1969. URL: https://doi.org/10.1090/S0002-9947-1969-0280205-0.
  7. Arnaud Carayol and Christof Löding. Uniformization in Automata Theory. In Proceedings of the 14th Congress of Logic, Methodology and Philosophy of Science Nancy, July 19-26, 2011, pages 153-178. London: College Publications, 2014. Google Scholar
  8. Alonzo Church. Logic, arithmetic and automata. In Proceedings of the International Congress of Mathematicians, pages 23-35, 1962. Google Scholar
  9. María Emilia Descotte, Diego Figueira, and Santiago Figueira. Closure properties of synchronized relations. In STACS, volume 126 of LIPIcs, pages 22:1-22:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  10. Joost Engelfriet. Top-down tree transducers with regular look-ahead. Math. Syst. Theory, 10:289-303, 1977. Google Scholar
  11. Joost Engelfriet and Sebastian Maneth. Macro tree translations of linear size increase are mso definable. SIAM Journal on Computing, 32(4):950-1006, 2003. Google Scholar
  12. Joost Engelfriet, Sebastian Maneth, and Helmut Seidl. Look-ahead removal for total deterministic top-down tree transducers. Theor. Comput. Sci., 616:18-58, 2016. Google Scholar
  13. Zoltán Ésik. Decidability results concerning tree transducers i. Acta Cybernetica, 5(1):1-20, 1980. Google Scholar
  14. Diego Figueira and Leonid Libkin. Synchronizing relations on words. Theory Comput. Syst., 57(2):287-318, 2015. Google Scholar
  15. Emmanuel Filiot, Ismaël Jecker, Christof Löding, and Sarah Winter. On equivalence and uniformisation problems for finite transducers. In ICALP, volume 55 of LIPIcs, pages 125:1-125:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  16. Emmanuel Filiot, Sebastian Maneth, Pierre-Alain Reynier, and Jean-Marc Talbot. Decision problems of tree transducers with origin. Inf. Comput., 261:311-335, 2018. Google Scholar
  17. Patrick C. Fischer and Arnold L. Rosenberg. Multitape one-way nonwriting automata. Journal of Computer and System Sciences, 2(1):88-101, 1968. URL: https://doi.org/10.1016/S0022-0000(68)80006-6.
  18. Zoltán Fülöp and Heiko Vogler. Syntax-directed semantics: Formal models based on tree transducers. Springer Science & Business Media, 2012. Google Scholar
  19. Timothy V. Griffiths. The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. Journal of the ACM, 15(3):409-413, 1968. Google Scholar
  20. Shizuya Hakuta, Sebastian Maneth, Keisuke Nakano, and Hideya Iwasaki. Xquery streaming by forest transducers. In 2014 IEEE 30th International Conference on Data Engineering, pages 952-963. IEEE, 2014. Google Scholar
  21. Michael Holtmann, Łukasz Kaiser, and Wolfgang Thomas. Degrees of lookahead in regular infinite games. In Foundations of Software Science and Computational Structures, volume 6014 of Lecture Notes in Computer Science, pages 252-266. Springer, 2010. URL: https://doi.org/10.1007/978-3-642-12032-9_18.
  22. Frederick A. Hosch and Lawrence H. Landweber. Finite delay solutions for sequential conditions. In ICALP, pages 45-60, 1972. Google Scholar
  23. Ralf Küsters and Thomas Wilke. Transducer-based analysis of cryptographic protocols. Information and Computation, 205(12):1741-1776, 2007. Google Scholar
  24. Christof Löding and Sarah Winter. Uniformization problems for tree-automatic relations and top-down tree transducers. In MFCS, volume 58 of LIPIcs, pages 65:1-65:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  25. Christof Löding and Sarah Winter. Synthesis of deterministic top-down tree transducers from automatic tree relations. Inf. Comput., 253:336-354, 2017. Google Scholar
  26. Andreas Maletti. Tree transformations and dependencies. In Conference on Mathematics of Language, pages 1-20. Springer, 2011. Google Scholar
  27. Andreas Maletti, Jonathan Graehl, Mark Hopkins, and Kevin Knight. The power of extended top-down tree transducers. SIAM Journal on Computing, 39(2):410-430, 2009. Google Scholar
  28. Kazutaka Matsuda, Kazuhiro Inaba, and Keisuke Nakano. Polynomial-time inverse computation for accumulative functions with multiple data traversals. Higher-Order and Symbolic Computation, 25(1):3-38, 2012. Google Scholar
  29. Tova Milo, Dan Suciu, and Victor Vianu. Typechecking for xml transformers. J. Comput. Syst. Sci., 66(1):66-97, 2003. URL: https://doi.org/10.1016/S0022-0000(02)00030-2.
  30. William C Rounds. Mappings and grammars on trees. Mathematical systems theory, 4(3):257-287, 1970. Google Scholar
  31. James W. Thatcher. Generalized² sequential machine maps. Journal of Computer and System Sciences, 4(4):339-367, 1970. Google Scholar
  32. Arie Van Deursen, Paul Klint, and Frank Tip. Origin tracking. Journal of Symbolic Computation, 15(5-6):523-545, 1993. Google Scholar
  33. Janis Voigtländer and Armin Kühnemann. Composition of functions with accumulating parameters. Journal of functional programming, 14(3):317, 2004. Google Scholar
  34. Sarah Winter. Uniformization problems for synchronizations of automatic relations on words. In ICALP, volume 107 of LIPIcs, pages 142:1-142:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. 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