Document Open Access Logo

When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?

Authors Sebastian Maneth, Helmut Seidl

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2020.134.pdf
  • Filesize: 0.53 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Formal languages and automata theory
Keywords
  • Top-Down Tree Transducers
  • Earliest Transformation
  • Linear Transducers
  • Uniform-copying Transucers
  • Removal of Look-ahead
  • Removal of Inspection

Metrics

Abstract

We consider two natural subclasses of deterministic top-down tree-to-tree transducers, namely, linear and uniform-copying transducers. For both classes we show that it is decidable whether the translation of a transducer with look-ahead can be realized by a transducer without look-ahead. The transducers constructed in this way, may still make use of inspection, i.e., have an additional tree automaton restricting the domain. We provide a second procedure which decides whether inspection can be removed and if so, constructs an equivalent transducer without inspection. The construction relies on a fixpoint algorithm that determines inspection requirements and on dedicated earliest normal forms for linear as well as uniform-copying transducers which can be constructed in polynomial time. As a consequence, equivalence of these transducers can be decided in polynomial time. Applying these results to deterministic bottom-up transducers, we obtain that it is decidable whether or not their translations can be realized by deterministic uniform-copying top-down transducers without look-ahead (but with inspection) - or without both look-ahead and inspection.

Cite As Get BibTex

Sebastian Maneth and Helmut Seidl. When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 134:1-134:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.134

Author Details

Sebastian Maneth
  • Universität Bremen, Germany
Helmut Seidl
  • TU München, Germany

References

  1. Krzysztof R. Apt and Gordon D. Plotkin. Countable nondeterminism and random assignment. J. ACM, 33(4):724-767, 1986. URL: https://doi.org/10.1145/6490.6494.
  2. Marie-Pierre Béal and Olivier Carton. Determinization of transducers over finite and infinite words. Theor. Comput. Sci., 289(1):225-251, 2002. URL: https://doi.org/10.1016/S0304-3975(01)00271-7.
  3. Jean Berstel. Transductions and context-free languages, volume 38 of Teubner Studienbücher : Informatik. Teubner, 1979. URL: http://www.worldcat.org/oclc/06364613.
  4. Adrien Boiret, Aurélien Lemay, and Joachim Niehren. Learning top-down tree transducers with regular domain inspection. In Proceedings of the 13th International Conference on Grammatical Inference, ICGI 2016, Delft, The Netherlands, October 5-7, 2016, pages 54-65, 2016. URL: http://proceedings.mlr.press/v57/boiret16.html.
  5. Christian Choffrut. Une caracterisation des fonctions sequentielles et des fonctions sous-sequentielles en tant que relations rationnelles. Theor. Comput. Sci., 5(3):325-337, 1977. URL: https://doi.org/10.1016/0304-3975(77)90049-4.
  6. Joost Engelfriet. Bottom-up and top-down tree transformations - A comparison. Mathematical Systems Theory, 9(3):198-231, 1975. URL: https://doi.org/10.1007/BF01704020.
  7. Joost Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, 10:289-303, 1977. URL: https://doi.org/10.1007/BF01683280.
  8. Joost Engelfriet, Sebastian Maneth, and Helmut Seidl. Look-ahead removal for total deterministic top-down tree transducers. Theor. Comput. Sci., 616:18-58, 2016. URL: https://doi.org/10.1016/j.tcs.2015.12.005.
  9. Emmanuel Filiot, Sebastian Maneth, Pierre-Alain Reynier, and Jean-Marc Talbot. Decision problems of tree transducers with origin. Inf. Comput., 261(Part):311-335, 2018. URL: https://doi.org/10.1016/j.ic.2018.02.011.
  10. Zoltán Fülöp and Andreas Maletti. Linking theorems for tree transducers. J. Comput. Syst. Sci., 82(7):1201-1222, 2016. URL: https://doi.org/10.1016/j.jcss.2016.05.003.
  11. Aurélien Lemay, Sebastian Maneth, and Joachim Niehren. A learning algorithm for top-down XML transformations. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2010, June 6-11, 2010, Indianapolis, Indiana, USA, pages 285-296, 2010. URL: https://doi.org/10.1145/1807085.1807122.
  12. William C. Rounds. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257-287, 1970. URL: https://doi.org/10.1007/BF01695769.
  13. James W. Thatcher. Generalized sequential machine maps. J. Comput. Syst. Sci., 4(4):339-367, 1970. URL: https://doi.org/10.1016/S0022-0000(70)80017-4.
  14. James W. Thatcher. There’s a lot more to finite automata theory than you would have thought. In Proc. 4th Ann. Princeton Conf. on Informations Sciences and Systems, pages 263-276, 1970. Also published in revised form under the title "Tree automata: an informal survey" in Currents in the Theory of Computing (ed. A. V. Aho), Prentice-Hall, 1973, 143-172. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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