Largest common prefix of a regular tree language

摘要

A family of tree automata of size n is presented such that the size of the largest common prefix (lcp) tree of all accepted trees is exponential in n. Moreover, it is shown that this prefix tree is not compressible via DAGs (directed acyclic graphs) or tree straight-line programs. We also show that determining whether or not the lcp trees of two given tree automata are equal is coNP-complete; the result holds even for deterministic bottom-up tree automata accepting finite tree languages. These results are in sharp contrast to the case of context-free string grammars.