LIPIcs.ICALP.2020.134.pdf
- Filesize: 0.53 MB
- 18 pages
Document
When Is a Bottom-Up Deterministic Tree Translation Top-Down Deterministic?
Authors
-
Part of:
Volume:
47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Colloquium on Automata, Languages, and Programming (ICALP) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-06-29
Cite AsGet 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
https://doi.org/10.4230/LIPIcs.ICALP.2020.134
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.
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
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- 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.
- 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.
- Jean Berstel. Transductions and context-free languages, volume 38 of Teubner Studienbücher : Informatik. Teubner, 1979. URL: http://www.worldcat.org/oclc/06364613.
- 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.
- 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.
- 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.
- Joost Engelfriet. Top-down tree transducers with regular look-ahead. Mathematical Systems Theory, 10:289-303, 1977. URL: https://doi.org/10.1007/BF01683280.
- 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.
- 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.
- 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.
- 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.
- William C. Rounds. Mappings and grammars on trees. Mathematical Systems Theory, 4(3):257-287, 1970. URL: https://doi.org/10.1007/BF01695769.
- 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.
-
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.
