Pebble Macro Tree Transducers with Strong Pebble Handling

• Autorzy: Fülöp Z. , Muzamel L.
• Języki publikacji: EN

Abstrakty

EN

We consider pebble macro tree transducers with call-by-name semantics and strong pebble handling. The latter means that the last dropped pebble can be lifted regardless of the position of the reading head. This tree transducer concept is a generalization of the pebblemacro tree transducer introduced by J. Engelfriet and S. Maneth in 2003, however we leave the original name untouched. Our main results are that (1) every n-pebble macro tree transformation can be characterized by the composition of an n-pebble tree transformation and a yield tree transformation, and (2) each n- pebble tree transformation can also be computed by an (n - 1)-pebble macro tree transformation. Using (1) and (2) we prove that every n-pebblemacro tree transformation appears as the composition of n+2 stay-macro tree transformations and hence, the inverses of n-pebble macro tree transformations preserve regularity. Finally, using the previous results, we show that the type checking problem for n-pebble macro tree transducers is decidable.

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 89, nr 2-3
• Strony: 207--257
• Opis fizyczny: bibliogr. 31 poz.

Twórcy

autor

Fülöp Z.

autor

Muzamel L.

• Department of Foundations of Computer Science University of Szeged Arpad tér 2., H-6720 Szeged, Hungary,

Bibliografia

• [1] Baker, B. S.: Composition of Top-Down and Bottom-Up tree Transductions, Inform. and Control, 41, 1979, 186-213.
• [2] Bex, G. J.,Maneth, S., Neven, F.: A formalmodel for an expressive fragment of XSLT, Information Systems, 27, 2002, 21-39.
• [3] Bojańczyk, M., Samuelides, M., Schwentick, T., Segoufin, L.: Expressive power of pebble automata, ICALP'06: Proceedings of 33rd International Colloquium on Automata, Languages and Programming, Springer Berlin / Heidelberg, 2006, ISBN 978-3-540-35904-3.
• [4] Courcelle, B., Franchi-Zannettacci, P.: Attribute grammars and recursive program schemes I-II, Theoret. Comput. Sci., 17, 1982, 163-191, 235-257.
• [5] Engelfriet, J.: Bottom-up and top-down tree transformations - A comparison, Math. Systems Theory, 9, 1975, 198-231.
• [6] Engelfriet, J.: Some open questions and recent results on tree transducers and tree languages, in: Formal language theory: perspectives and open problems (R. Book, Ed.), New York, Academic Press, 1980, 241-286.
• [7] Engelfriet, J.: Tree transducers and syntax-directed semantics, Technical Report Memorandum 363, Technische Hogeschool Twente, March 1981, Also in: Proceedings of the Colloquium on Trees in Algebra and Programming (CAAP 1992), Lille, France 1992.
• [8] Engelfriet, J., Hoogeboom, H. J.: Automata with nested pebbles capture first-order logic with transitive closure., Technical Report 05-02, Leiden University, The Netherlands, April 2005.
• [9] Engelfriet, J., Maneth, S.: A Comparison of Pebble Tree Transducers with Macro Tree Transducers, Acta Informatica, 39, 2003, 613-698.
• [10] Engelfriet, J., Schmidt, E.: IO and OI, Part II., J. Comput. System Sci., 16(1), 1978, 67-99.
• [11] Engelfriet, J., Schmidt, E. M.: IO and OI, Part I., J. Comput. System Sci., 15(3), 1977, 328-58.
• [12] Engelfriet, J., Vogler, H.: Macro tree transducers, J. Comput. System Sci., 31, 1985, 71-146.
• [13] Engelfriet, J., Vogler, H.: Pushdown machines for the macro tree transducer, Theoret. Comput. Sci., 42(3), 1986, 251-368.
• [14] Fischer, M.: Grammars with macro-like productions, Ph.D. Thesis, Harvard University, Massachusetts, 1968.
• [15] Fülöp, Z.: On attributed tree transducers, Acta Cybernet., 5, 1981, 261-279.
• [16] Fülöp, Z.,Muzamel, L.: Circularity and Decomposition Results for PebbleMacro Tree Transducers, Journal of Automata, Languages and Combinatorics, 13(1), 2008, 3-44.
• [17] Fülöp, Z., Vogler, H.: Syntax-Directed Semantics-FormalModels Based on Tree Transducers, Monographs in Theoretical Computer Science, An EATCS Series, Springer-Verlag, 1998.
• [18] Gécseg, F., Steinby, M.: Tree Automata, Akadémiai Kiad´o, Budapest, 1984.
• [19] Gécseg, F., Steinby, M.: Tree Languages, in: Handbook of Formal Languages (G. Rozenberg, A. Salomaa, Eds.), vol. 3, Springer-Verlag, 1997, 1-68.
• [20] Irons, E. T.: A syntax directed compiler for ALGOL 60, Comm. of the ACM, 4, 1961, 51-55.
• [21] Knuth, D. E.: Semantics of context-free languages, Math. Systems Theory, 2, 1968, 127-145.
• [22] Knuth, D. E.: Semantics of Context-Free Languages: Correction, Math. Systems Theory, 5(1), 1971, 95-96, Errata of [21].
• [23] Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML Type Checking with Macro Tree Transducers, Proceedings of the 24th ACM Symposium on Principles of Database Systems (PODS' 05), ACM Press, 2005.
• [24] Maneth, S., Neven, F.: Recursive structured document transformation, Research issues in structured and semistructured database programming - Revised papers DBLP 99 (R. Connor, R. Mendelzon, Eds.), 1949, Springer-Verlag, 2001.
• [25] Milo, T., Suciu, D., Vianu, V.: Typechecking for XML transformers, J. of Comput. Syst. Sci., 66, 2003, 66-97.
• [26] Muscholl, A., Samuelides, M., Segoufin, L.: Complementing Deterministic Tree-Walking Automata, Information Processing Letters, 99, 2006, 33-39.
• [27] Rounds, W.: Mappings and grammars on trees, Math. Systems Theory, 4, 1970, 257-287.
• [28] Thatcher, J.: Generalized2 sequential machine maps, 1969, IBM Res. Report RC 2466.
• [29] Vianu, V.: A Web Odyssey: From Codd to XML, Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS' 01), ACM Press, 2001.
• [30] Vogler, H.: Functional description of the contextual analysis in block-structured programming languages: a case study of tree transducers, Science of Comput. Prog., 16, 1991, 251-275.
• [31] Wilhelm, R., Maurer, D.: Compiler Design, Addison-Wesley, 1995.