Largest common prefix of a regular tree language (Q5919000)

The contribution discusses the largest common prefix computation for regular tree languages. The class of regular tree languages is the class of tree languages recognizable by (deterministic) bottom-up tree automata. The largest common prefix is the largest common part starting at the root of the trees that is common to all trees recognized by the tree automaton. Any such potential nontrivial largest common prefix is relevant for several normalization procedures (e.g., for deterministic top-down tree transducers). For every nonnegative integer \(n\), a tree automaton of size linear in \(n\) is presented such that its largest common prefix has exponential size in \(n\) and cannot be compressed significantly by standard methods like directed acyclic graphs (DAGs) and straight-line programs (in other words, by sharing common subtrees). This is an extension of a family of string automata that is difficult to determinize. On the other hand, if a deterministic top-down tree automaton is given, then a DAG-representation of the largest common prefix can be computed in linear time. Finally, it is demonstrated that the problem of checking whether the largest common prefix of two given bottom-up tree automata is equal is coNP-complete. This is achieved by a reduction from the complement of 3-SAT. The contribution is well written and nicely illustrated. The writing is precise and full proof details are provided for all claims. Some background on regular tree languages is assumed, but otherwise the contribution can be fully appreciated by any graduate-level reader.