Abstract: While in Chapter 5 we defined patterns as an approach to subtree extraction, in this chapter we introduce an alternative approach called path expressions. While patterns use structural constraints for matching subtrees, path expressions use “navigation,” which specifies a sequence of movements on the tree and makes checks on the visited nodes. In practice, path expressions tend to be more concise since they do not require conditions to be specified for the nodes not on the path. In theory, however, path expressions are strictly less expressive (i.e., they cannot express all regular tree languages) unless sufficient extensions are made. In this chapter we first review path expressions used in actual XML processing and then consider a refinement called caterpillar expressions. After this, we study the corresponding automata formalism, called tree-walking automata, and compare their expressiveness with tree automata.
Publication Year: 2010
Publication Date: 2010-11-04
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot