caa a22 4500 465821332 CHVBK 20180323112136.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF01933209 doi (NATIONALLICENCE)springer-10.1007/BF01933209 Unifications, deunifications, and their complexity [Elektronische Daten] [Heikki Mannila, Esko Ukkonen] The execution of a Prolog program can be viewed as a sequence of unifications and backtracks over unifications. We study the time requirement of executing a sequence of such operations (the unify-deunify problem). It is shown that the well-known set union problem is reducible to this problem, even in the case when no function symbols are allowed (the Datalog unify-deunify problem). As the set union problem requires nonlinear time on a large class of algorithms, the same holds for the unify-deunify problem. Thus the linearity of single unifications does not give a complete picture of the time complexity of Prolog primitives. We discuss the methods for executing sequences of Datalog unifications used in Prolog interpreters and show that some of them require even quadratic time in the worst case. Complementing these results, we show that if the number of variables occurring in one clause is bounded by a constant, then the Datalog unify-deunify problem can be solved in linear time. BIT Foundations, 1990 F.2.2 nationallicence D.3.4 nationallicence Mannila Heikki Department of Computer Science, University of Helsinki, Teollisuuskatu 23, SF-00510, Helsinki, Finland aut Ukkonen Esko Department of Computer Science, University of Helsinki, Teollisuuskatu 23, SF-00510, Helsinki, Finland aut BIT Numerical Mathematics Kluwer Academic Publishers 30/4(1990-12-01), 599-619 0006-3835 30:4<599 1990 30 10543 https://doi.org/10.1007/BF01933209 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF01933209 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Mannila Heikki Department of Computer Science, University of Helsinki, Teollisuuskatu 23, SF-00510, Helsinki, Finland aut NATIONALLICENCE 700 1- Ukkonen Esko Department of Computer Science, University of Helsinki, Teollisuuskatu 23, SF-00510, Helsinki, Finland aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Kluwer Academic Publishers 30/4(1990-12-01), 599-619 0006-3835 30:4<599 1990 30 10543 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer