HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item:
Title: Caterpillars, context, tree automata and tree pattern matching
Authors: Brüggemann-Klein, Anne
Wood, Derick
Keywords: Caterpillar expressions
Tree automata
Tree pattern matching
Issue Date: 2000
Citation: Proceedings of the Fourth International Conference on Developments in Formal Language Theory (DLT 99) : Foundations, Applications and Perspectives, G. Rozenberg and W. Thomas (Eds), World Scientific Publishing Co. Pte. Ltd., Singapore, (2000), 270-285
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-02
Abstract: We present a novel, yet simple, technique for the specifiction of context in structured documents that we call caterpillar expressions. Although we are primarily applying this technique in the specification of context-dependent style sheets for HTML, SGML and XML documents, it can also be used for query specification for structured documents, as we shall demonstrate, and for the specification of computer program transformations. From a conceptual point of view, structured documents are trees, and one of the oldest and best-established techniques to process trees and, hence, structured documents are tree automata. We present a number of theoretical results that allow us to compare the expressive power of caterpillar expressions and caterpillar automata, their companions, to the expressive power of tree automata. In particular, we demonstrate that each caterpillar expression describes a regular tree language that is, hence, recognizable by a tree automaton. Finally, we employ caterpillar expressions for tree pattern matching. We demonstrate that caterpillar automata are able to solve tree-pattern-matching problems for some, but not all, types of tree inclusion that Kilpeläinen investigated in his PhD thesis. In simulating tree pattern matching with caterpillar automata, we reprove some of Kilpeläinen's results in a uniform framework.
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200002.pdf241KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.