Deduction in Existential Conjunctive First-Order Logic: an Algorithm and Experiments - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports Year : 2010

Deduction in Existential Conjunctive First-Order Logic: an Algorithm and Experiments

Abstract

We consider the deduction problem in the existential conjunctive fragment of first-order logic with atomic negation. This problem can be recast in terms of other database and artificial intelligence problems, namely query containment, clause entailment and boolean query answering. We refine an algorithm scheme that was proposed for query containment, which itself improves other known algorithms in databases. To study it experimentally, we build a random generator and analyze the influence of several parameters on the problem instance difficulty. Using this methodology, we experimentally compare several heuristics. We also present preliminary results on the comparison of our algorithm, which is based on homomorphism checks, to the theorem prover Prover9, which is based on the resolution method.
No file

Dates and versions

lirmm-00463579 , version 1 (12-03-2010)

Identifiers

  • HAL Id : lirmm-00463579 , version 1

Cite

Khalil Ben Mohamed, Michel Leclère, Marie-Laure Mugnier. Deduction in Existential Conjunctive First-Order Logic: an Algorithm and Experiments. RR-10010, 2010, pp.20. ⟨lirmm-00463579⟩
257 View
0 Download

Share

Gmail Facebook X LinkedIn More