... subgraphs of the tree, for instance using the sharing graphs of Lamping [9], or the straight-line (linear) context-free tree (SLT) grammars of Busatto, Lohrey, and Maneth [3]. The recent “TreeRePair” compressor [11] shrinks the (edge) size of typical XML document trees by a factor of four, with respect to the minimal unranked DAG (cf. Table 4 in [11]). It was shown by Lohrey and Maneth [10] that tree automata and navigational XPath can be evaluated in PTIME over SLT grammars, without prior decompression. This is used to build a system for selectivity estimation for XPath by Fisher and Maneth [5]. Roughly speaking, the idea is to translate the XPath query into a certain tree automaton, and to execute this automaton over the SLT grammar. In this paper we make these constructions more prePermission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a ...