scientific article; zbMATH DE number 3974342
[For the entire collection see Zbl 0587.00020.] This paper investigates the computational complexity question for intelligent backtracking based on finding either all or particular maximal unifiable or minimal nonunifiable subsets of constraints. The following results are stated and proved: the 0-X-1 unifiable subset, the largest maximal unifiable subset, the bounded unifiability, and the bounded resolution unifiability problem are NP-complete, respectively. Corresponding results on minimal nonunifiability are also NP-complete problems. All these problems have relevance to the design of improved backtracking in theorem provers and PROLOG implementations using standard or non- standard unification. These results explain why heuristic and approximate strategies are necessary in (semi-) intelligent backtracking. Average time complexity should also be interesting to be analyzed.
- Intractable unifiability problems and backtracking
- Maximal unifiable subsets and minimal non-unifiable subsets
- Intelligent backtracking in deduction systems by means of extended unification graphs
- A theoretical evaluation of selected backtracking algorithms.
- scientific article; zbMATH DE number 3995082
- Maximal unifiable subsets and minimal non-unifiable subsets
- Intelligent backtracking in deduction systems by means of extended unification graphs
- Intractable unifiability problems and backtracking
- Incremental constraint satisfaction for equational logic programming
- Intelligent backtracking in \(\text{CLP}(\Re)\)
- Recursive unsolvability of a problem of expressibility in the logic of provability
- scientific article; zbMATH DE number 3858459 (Why is no real title available?)
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740274)