Mannila, Heikki; Ukkonen, Esko The set union problem with backtracking. (English) Zbl 0596.68039 Automata, languages and programming, Proc. 13th Int. Colloq., Rennes/France 1986, Lect. Notes Comput. Sci. 226, 236-243 (1986). Summary: [For the entire collection see Zbl 0587.00019.] The classical set union problem is to manipulate a partition of \(U=\{1,2,...,n\}\) under the operations find an union. We study a variant of this problem, where backtracking over the union operations is possible with the deunion operation. An implementation is developed to on-line perform an intermixed sequence of m finds, k unions and at most k deunions in \(O((m+k)\log \log n)\) steps. An \(O(k+m \log n)\) method is also given. The problem considered is motivated by questions arising in the implementation of the programming language Prolog. Cited in 2 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 05A17 Combinatorial aspects of partitions of integers Keywords:deunion Citations:Zbl 0587.00019 PDF BibTeX XML OpenURL