Undecidability of the Horn-clause implication problem
Authors:
- L. PacholskiLPL. Pacholski
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 354-362
Abstract
The authors prove that the problem 'given two Horn clauses H/sub 1/=( alpha /sub 1/ V-product alpha /sub 2/ to beta ) and H/sub 2/=( gamma /sub 1/ V-product . . . V-product gamma /sub k/ to delta ), where alpha /sub i/, beta , gamma /sub i/, delta are atomic formulas, decide if H/sub 2/, is a consequence of H/sub 1/' is not recursive. This solves one of the last open decidability problems concerning formulas in pure predicate logic (i.e. without equality symbol). The proof depends on a thorough analysis of derivation trees of one rule of inference with two premisses and one conclusion, and it may have further applications.Keywords
This publication has 16 references indexed in Scilit:
- The undecidability of the semi-unification problem1990
- Implication Algorithms for Classes of Horn Clauses1988
- The Implication Problem for Functional and Inclusion Dependencies is UndecidableSIAM Journal on Computing, 1985
- The unsolvability of the Gödel class with identityThe Journal of Symbolic Logic, 1984
- Embedded implicational dependencies and their inference problem1981
- Unsolvable Problems1977
- The decision problem for equational bases of algebrasAnnals of Mathematical Logic, 1976
- The decision problem for standard classesThe Journal of Symbolic Logic, 1976
- On spectra, and the negative solution of the decision problem for identities having a finite nontrivial modelThe Journal of Symbolic Logic, 1975
- The decision problem for formulas with a small number of atomic subformulasThe Journal of Symbolic Logic, 1973