Unifications, deunifications, and their complexity (Q1173920)

The time complexity of the Datalog unify-deunify problem (DUDP) is considered, i.e. of the problem of on-line execution of sequences of operations of unification and deunification of variables and constants. Pointer machines are used for execution. DUDP is easily reducible to the union-find-deunion problem (UFDP) considered by \textit{J. Westbrook} and \textit{R. E. Tarjan} [SIAM J. Comput. 18(1), 1-11 (1989; Zbl 0679.68039)] and generalizing the well-known union-find problem (UFP), i.e. any (separable) algorithm for a pointer machine solving UFDP can be easily transformed into a (separable) algorithm solving DUDP with a linear increasing of execution time. Using Westbrook and Tarjan's result it gives the upper bound \(O(\log n\log \log n)\) for amortized time complexity of DUDP. Some reductions of UFP and UFDP to DUDP are constructed. The known lower bounds of time complexity for UFP and UFDP hold for DUDP. However, at least for UFDP some additional reasoning is necessary since the reduction described gives a somewhat more general kind of machines that that used in other investigations in order to obtain these lower bounds; in a private communication to me Prof. Mannila noted that these problems do not occur for a translation to DUDP with the lower bound \(O(n+m\alpha(m,n))\) for UFP which was recently shown by \textit{J. La Poutre} for general pointer machines.