article

A comparison of pebble tree transducers with macro tree transducers

Authors:

Joost Engelfriet,

Sebastian ManethAuthors Info & Claims

Acta Informatica, Volume 39, Issue 9

Pages 613 - 698

https://doi.org/10.1007/s00236-003-0120-0

Published: 01 August 2003 Publication History

Abstract

The n -pebble tree transducer was recently proposed as a model for XML query languages. The four main results on deterministic transducers are: First, (1) the translation $\tau$ of an n -pebble tree transducer can be realized by a composition of n +1 0-pebble tree transducers. Next, the pebble tree transducer is compared with the macro tree transducer, a well-known model for syntax-directed semantics, with decidable type checking. The -pebble tree transducer can be simulated by the macro tree transducer, which, by the first result, implies that (2) $\tau$ can be realized by an ( n +1)-fold composition of macro tree transducers. Conversely, every macro tree transducer can be simulated by a composition of 0-pebble tree transducers. Together these simulations prove that (3) the composition closure of n -pebble tree transducers equals that of macro tree transducers (and that of 0-pebble tree transducers). Similar results hold in the nondeterministic case. Finally, (4) the output languages of deterministic n -pebble tree transducers form a hierarchy with respect to the number n of pebbles.

References

[1]

Alblas H., Melichar B. (eds.) International Summer School on Attribute grammars, applications and systems , vol. 545 of LNCS . Springer-Verlag, 1991.

[2]

Alon N., Milo T., Neven F., Suciu D., Vianu V. Typechecking XML views of relational databases. In Proceedings of the 16th Annual IEEE Symposium on Logic in Computer Science - (LICS'2001) . IEEE, 2001.

Digital Library

[3]

Alon N., Milo T., Neven F., Suciu D., Vianu V. XML with data values: Typechecking revisited. In Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'2001) , pp. 138-149. ACM Press, 2001.

[4]

Aho A.V., Ullman J.D. Translations on a context-free grammar. Inform. and Control 19: 439-475, 1971.

[5]

Bex G.J., Maneth S., Neven F. A formal model for an expressive fragment of XSLT. Information Systems 27: 21-39, 2002.

Digital Library

[6]

Courcelle B., Franchi-Zannettacci P. Attribute grammars and recursive program schemes. Theoret. Comput. Sci . 17: 163-191 and 235-257, 1982.

[7]

Chytil M.P., Jákl V. Serial composition of 2-way finite-state transducers and simple programs on strings. In: Salomaa A., Steinby M. (eds.) Proceedings of the 15th International Colloquium on Automata, Languages and Programming - (ICALP'77) , volume 52 of LNCS , pp. 135-147. Springer-Verlag, 1977.

[8]

Courcelle B. Fundamental properties of infinite trees. Theoret. Comput. Sci . 25: 95- 169, 1983.

[9]

Drewes F., Engelfriet J. Decidability of finiteness of ranges of tree transductions. Inform. and Comput . 145: 1-50, 1998.

[10]

Dershowitz N., Jouannaud J.P. Rewrite systems. In: van Leeuwen J. (ed.) Handbook of Theoretical Computer Science, vol. B , chapt. 6, pp. 243-320. Elsevier, 1990.

[11]

Deransart P., Jourdan M., Lorho B. Attribute Grammars, Definitions and Bibliography , vol. 323 of LNCS . Springer-Verlag, 1988.

[12]

Engelfriet J., Filè G. The formal power of one-visit attribute grammars. Acta Informatica 16: 275-302, 1981.

Digital Library

[13]

Engelfriet J., Hoogeboom H.J. Tree-walking pebble automata. In: Karhumäki J., Maurer H., Paun, Gh., Rozenberg G. (eds.) Jewels are forever, contributions to Theoretical Computer Science in honor of Arto Salomaa , vol. 1644 of LNCS , pp. 72-83. Springer-Verlag, 1999.

[14]

Engelfriet J., Maneth S. Macro tree transducers, attribute grammars, and MSO definable tree translations. Inform. and Comput . 154: 34-91, 1999.

[15]

Engelfriet J., Maneth S. Macro tree translations of linear size increase are MSO definable. Technical Report 01-08, Leiden University, 2001. To appear in SIAM J. Comput .

[16]

Engelfriet J., Maneth S. Output string languages of compositions of deterministic macro tree transducers. J. of Comp. Syst. Sci . 64: 350-395, 2002.

[17]

Engelfriet J., Maneth S. Two-way finite state transducers with nested pebbles. In: Diks K., Rytter W. (eds.) Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science - (MFCS'2002) , vol. 2430 of LNCS , pp. 234-244. Springer-Verlag, 2002.

[18]

Engelfriet J. Some open questions and recent results on tree transducers and tree languages. In: Book R.V. (ed.) Formal language theory; perspectives and open problems . New York, Academic Press, 1980.

[19]

Engelfriet J. Tree transducers and syntax-directed semantics. Technical Report Memorandum 363, Technische Hogeschool Twente, 1981. Also in: Proceedings of 7th Colloquium on Trees in Algebra and Programming (CAAP 1982), Lille, France, 1982.

[20]

Engelfriet J. Three hierarchies of transducers. Math. Systems Theory 15: 95-125, 1982.

[21]

Engelfriet J. Context-free grammars with storage. Technical Report 86-11, University of Leiden, 1986.

[22]

Engelfriet J., Rozenberg G., Slutzki G. Tree transducers, L systems, and two-way machines. J. of Comp. Syst. Sci . 20: 150-202, 1980.

[23]

Engelfriet J., Schmidt E.M. IO and OI, Part I. J. of Comp. Syst. Sci . 15: 328-353, 1977. And Part II, J. of Comp. Syst. Sci . 16: 67-99, 1978.

[24]

Engelfriet J., Vogler H. Macro tree transducers. J. of Comp. Syst. Sci . 31: 71-146, 1985.

[25]

Engelfriet J., Vogler H. Pushdown machines for the macro tree transducer. Theoret. Comput. Sci . 42: 251-368, 1986.

[26]

Engelfriet J., Vogler H. High level tree transducers and iterated pushdown tree transducers. Acta Informatica 26: 131-192, 1988.

Digital Library

[27]

Fischer M.J. Grammars with macro-like productions . PhD thesis, Harvard University, Massachusetts, 1968.

[28]

Fülöp Z., Maneth S. Domains of partial attributed tree transducers. Inform. Proc. Letters 73: 175-180, 2000.

Digital Library

[29]

Franchi-Zannettacci P. Attributes semantiques et schemas de programmes . PhD thesis, Université de Bordeaux I, 1982. Thèse d'Etat.

[30]

Fülöp Z. On attributed tree transducers. Acta Cybernetica 5: 261-279, 1981.

[31]

Fülöp Z., Vogler H. Syntax-Directed Semantics - Formal Models based on Tree Transducers . EATCS Monographs on Theoretical Computer Science (Brauer W., Rozenberg G., Salomaa A. (eds.) Springer-Verlag, 1998.

[32]

Fülöp Z., Vogler H. A characterization of attributed tree transformations by a subclass of macro tree transducers. Theory Comput. Systems 32: 649-676, 1999.

[33]

Globerman N., Harel D. Complexity results for two-way and multi-pebble automata and their logics. Theoret. Comput. Sci . 169: 161-184, 1996.

[34]

Ginsburg S. Algebraic and Automata-Theoretic Properties of Formal Languages . North-Holland, Amsterdam, 1975.

Digital Library

[35]

Géecseg F., Steinby M. Tree Automata . Akadémiai Kiadó, Budapest, 1984.

[36]

Gécseg F., Steinby M. Tree automata. In: Rozenberg G., Salomaa A. (eds.) Handbook of Formal Languages, vol. 3 , chapt. 1. Springer-Verlag, 1997.

[37]

Goguen J.A., Thatcher J.W., Wagner E.G., Wright J.B. Initial algebra semantics and continuous algebras. J. ACM 24: 68-95, 1977.

Digital Library

[38]

Irons E.T. A syntax directed compiler for ALGOL 60. Comm. Assoc. Comput. Mach . 4: 51-55, 1961.

[39]

Kamimura T. Tree automata and attribute grammars. Inform. and Control 57: 1-20, 1983.

Digital Library

[40]

Klop J.W. Term rewrite systems. In: Abramsky S., Gabbay D.M., Maibaum T.S.E. (eds.) Handbook of Logic in Computer Science, vol. 2 . Oxford Science Publications, 1992.

[41]

Kolb H.-P., Michaelis J., Mönnich U., Morawietz F. An operational and denotational approach to non-context-freeness. To appear in Theoret. Comput. Sci . .

[42]

Knuth D.E. Semantics of context-free languages. Math. Systems Theory 2: 127-145, 1968. (Corrections in Math. Systems Theory 5: 95-96, 1971).

[43]

Kühnemann A. Benefits of tree transducers for optimizing functional programs. In: Arvind V., Ramanujam R. (eds.) Proceedings of the 18th Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS'98) , vol. 1530 of LNCS , pp. 146-157. Springer-Verlag, 1998.

[44]

Kühnemann A., Vogler H. Synthesized and inherited functions--a new computational model for syntax-directed semantics. Acta Informatica 31: 431-477, 1994.

Digital Library

[45]

Kühnemann A., Vogler H. Attributgrammatiken . Vieweg-Verlag, 1997.

[46]

Maneth S. The complexity of compositions of deterministic tree transducers. In: Agrawal M., Seth A. (eds.) Proceedings of the 22nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2002) , vol. 2556 of LNCS , pp. 265-276. Springer-Verlag, 2002.

[47]

Michaelis J., Mönnich U., Morawietz F. On minimalist attribute grammars and macro tree transducers. In: Rohrer C., Rossdeutscher A., Kamp H. (eds.) Linguistic Form and its Computation , pp. 287-326. CSLI Publications, Stanford, 2001.

[48]

Maneth S., Neven F. Recursive structured document transformations. In: Connor R., Mendelzon A. (eds.) Research Issues in Structured and Semistructured Database Programming - Revised Papers DBPL'99 , vol. 1949 of LNCS , pp. 80-98. Springer-Verlag, 2000.

[49]

Milo T., Suciu D., Vianu V. Typechecking for XML transformers. J. of Comp. Syst. Sci. 66: 66-97, 2003.

Digital Library

[50]

Milo T., Suciu D., Vianu V. Typechecking for XML transformers. In Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'2000) , pp. 11-22. ACM Press, 2000.

Digital Library

[51]

Neven F., Schwentick T., Vianu V. Towards regular languages over infinite alphabets. In Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS'01) , vol. 2136 of LNCS . Springer-Verlag, 2001.

[52]

Paakki J. Attribute grammar paradigms - a high-level methodology in language implementation. ACM Computing Surveys 27: 196-255, 1995.

Digital Library

[53]

Papakonstantinou Y., Vianu V. DTD inference for views of XML data. In Proceedings of the 19th ACM Symposium on Principles of Database Systems (PODS'2000) , pp. 35-46, ACM Press 2000.

Digital Library

[54]

Rounds W.C. Mappings and grammars on trees. Math. Systems Theory 4: 257-287, 1970.

[55]

Suciu D. The XML typechecking problem. SIGMOD Record 31: 89-96, 2002.

Digital Library

[56]

Thatcher J.W. Generalized sequential machine maps. J. of Comp. Syst. Sci . 4: 339-367, 1970.

[57]

Tozawa A. Towards static type checking for XSLT. In Proceeding of the ACM Symposium on Document Engineering , pp. 18-27. ACM Press, 2001.

[58]

Vianu V. A Web Odyssey: From Codd to XML. In Proceedings of the 20th ACM Symposium on Principles of Database Systems (PODS'2001) , pp. 1-15. ACM Press, 2001.

[59]

Vogler H. Functional description of the contextual analysis in block-structured programming languages: a case study of tree transducers. Science of Computer Programming 16: 251-275, 1991.

Digital Library

[60]

Voigtländer J. Conditions for efficiency improvement by tree transducer composition. In Proceedings of the 13th International Conference on Rewriting Techniques and Applications (RTA 2002) , vol. 2378 of LNCS , pp. 222-236. Springer-Verlag, 2002.

[61]

Wilhelm R., Maurer D. Compiler Design . Addison-Wesley, 1995.

Cited By

Kiefer S(2024)Polyregular Functions Characterisations and RefutationsDevelopments in Language Theory10.1007/978-3-031-66159-4_2(13-21)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-66159-4_2
Maneth SSeidl H(2023)Deciding origin equivalence of weakly self-nesting macro tree transducersInformation Processing Letters10.1016/j.ipl.2022.106332180:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.ipl.2022.106332
Lemerre M(2023)Reverse Template Processing Using Abstract InterpretationStatic Analysis10.1007/978-3-031-44245-2_18(403-433)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44245-2_18
Show More Cited By

Index Terms

A comparison of pebble tree transducers with macro tree transducers

Index terms have been assigned to the content through auto-classification.

Recommendations

Pebble Macro Tree Transducers with Strong Pebble Handling

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 ...
Pebble Macro Tree Transducers with Strong Pebble Handling

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 ...
Circularity, composition, and decomposition results for pebble macro tree transducers

The pebble tree transducer is a model for XML query languages while the macro tree transducer is a well-known model for syntax-directed semantics. We consider their combination, called pebble macro tree transducer (using outside-in semantics). We define ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Acta Informatica

Acta Informatica Volume 39, Issue 9

August 2003

88 pages

ISSN:0001-5903

Issue’s Table of Contents

Copyright © Copyright © 2003 Springer-Verlag.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 August 2003

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kiefer S(2024)Polyregular Functions Characterisations and RefutationsDevelopments in Language Theory10.1007/978-3-031-66159-4_2(13-21)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-66159-4_2
Maneth SSeidl H(2023)Deciding origin equivalence of weakly self-nesting macro tree transducersInformation Processing Letters10.1016/j.ipl.2022.106332180:COnline publication date: 1-Feb-2023
https://dl.acm.org/doi/10.1016/j.ipl.2022.106332
Lemerre M(2023)Reverse Template Processing Using Abstract InterpretationStatic Analysis10.1007/978-3-031-44245-2_18(403-433)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44245-2_18
Seidl HManeth SKemper G(2018)Equivalence of Deterministic Top-Down Tree-to-String Transducers Is DecidableJournal of the ACM10.1145/318265365:4(1-30)Online publication date: 12-Apr-2018
https://dl.acm.org/doi/10.1145/3182653
Engelfriet J(2015)Two-way pebble transducers for partial functions and their compositionActa Informatica10.1007/s00236-015-0224-352:7-8(559-571)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1007/s00236-015-0224-3
Fülöp ZVogler H(2014)Forward and backward application of symbolic tree transducersActa Informatica10.1007/s00236-014-0197-751:5(297-325)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/s00236-014-0197-7
Matsuda KInaba KNakano KKiselyov OThompson S(2012)Polynomial-time inverse computation for accumulative functions with multiple data traversalsProceedings of the ACM SIGPLAN 2012 workshop on Partial evaluation and program manipulation10.1145/2103746.2103752(5-14)Online publication date: 23-Jan-2012
https://dl.acm.org/doi/10.1145/2103746.2103752
Veanes MHooimeijer PLivshits BMolnar DBjorner NField JHicks M(2012)Symbolic finite state transducersProceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages10.1145/2103656.2103674(137-150)Online publication date: 25-Jan-2012
https://dl.acm.org/doi/10.1145/2103656.2103674
Veanes MHooimeijer PLivshits BMolnar DBjorner N(2012)Symbolic finite state transducersACM SIGPLAN Notices10.1145/2103621.210367447:1(137-150)Online publication date: 25-Jan-2012
https://dl.acm.org/doi/10.1145/2103621.2103674
Matsuda KInaba KNakano K(2012)Polynomial-time inverse computation for accumulative functions with multiple data traversalsHigher-Order and Symbolic Computation10.1007/s10990-013-9097-825:1(3-38)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s10990-013-9097-8
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents