Formal Grammars for Linguistic Treebank Queries

There has been recent interest in looking at what is required for a tree query language for linguis-tic corpora. One approach is to start from exist-ing formal machinery, such as tree grammars and automata, to see what kind of machine is an ap-propriate underlying one for the query language. The goal of the paper is then to examine what is an appropriate machine for a linguistic tree query language, with a view to future work dening a query language based on it. In this paper we review work relating XPath to regular tree gram-mars, and as the paper's rst contribution show how regular tree grammars can also be a basis for extensions proposed for XPath for common lin-guistic corpus querying. As the paper's second contribution we demonstrate that, on the other hand, regular tree grammars cannot describe a number of structures of interest; we then show that, instead, a slightly more powerful machine is appropriate, and indicate how linguistic tree query languages might be augmented to include this extra power.