On the Implementation of Tree Automata: Limitations of the Naive Approach
Hendrik Maryns · 2006
Monadic Second Order logic (MSO) has been used as a formalism to describe Government and Binding rules. It also lends itself to be used as a query language. Main arguments are its expressive power and linear data complexity. Particularly in the domain of tree banks, where the size of the data is much bigger than the size of the query, the data complexity is an influential factor. It is known since the late 1960s that an MSO formula can be translated into a tree automaton. These results also predict an more than exponential blowup of the number of states of the tree automaton corresponding to the number of quantifier alternations in the formula. If one refrains from writing complicated formulae and thus avoids the theoretical blowup, one could hope the result becomes practically usable to write a query tool for tree banks. It is shown here that another problem arises: even with few quantifier alternations the transition tables get too big very soon. This is illustrated by a straightforward implementation of tree automata: by taking the definition in its mathematical sense, and translating every element into an equivalent computer language construct. This was done in a prototype Java version of the tool described above. I describe why this approach reaches its limits all too soon, due to the above problem.