Another variation on the common subexpression problem (Q685700)

An algorithm for deciding the equivalence of two deterministic finite ascending (frontier-to-root) tree automata is presented and analyzed. The algorithm constructs a Nerode equivalence on the disjoint union of the state sets of the two automata by means of special test sets of `pointed trees'. For binary trees with a fixed alphabet the algorithm is shown to perform in time \({\mathcal O}(n^ 2)\), where \(n\) is the total number of states. Since this is also the order of the input size, it can be deduced that the complexity of the equivalence problem is linear in the input alphabet and \({\mathcal O}(n^ 2)\) in the number of states. For general ranked alphabets with maximal rank \(k\), the complexity is shown to be \({\mathcal O}(n^ k)\). The case of incomplete automata with sparse transition tables is also analysed. Finally, the parallel complexity of the problem is considered and it is shown to be logspace-complete for \(P\). In the introduction the authors point out that the present problem is closely related to some other problems, the common subexpression problem, for example.