×

Subsumer: a Prolog \(\theta\)-subsumption engine. (English) Zbl 1237.68180

Hermenegildo, Manuel (ed.) et al., Technical communications of the 26th international conference on logic programming (ICLP 2010), July 16–19, 2010, Edinburgh, Scotland, UK. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-939897-17-0). LIPIcs – Leibniz International Proceedings in Informatics 7, 172-181, electronic only (2010).
Summary: State-of-the-art \(\theta\)-subsumption engines like Django (C) and Resumer2 (Java) are implemented in imperative languages. Since \(\theta\)-subsumption is inherently a logic problem, in this paper we explore how to efficiently implement it in Prolog.
\(\theta\)-subsumption is an important problem in computational logic and particularly relevant to the inductive logic programming (ILP) community as it is at the core of the hypotheses coverage test which is often the bottleneck of an ILP system. Also, since most of those systems are implemented in Prolog, they can immediately take advantage of a Prolog based \(\theta\)-subsumption engine.
We present a relatively simple (\(\approx 1000\) lines in Prolog) but efficient and general \(\theta\)-subsumption engine, Subsumer. Crucial to Subsumer’s performance is the dynamic and recursive decomposition of a clause in sets of independent components. Also important are ideas borrowed from constraint programming that empower Subsumer to efficiently work on clauses with up to several thousand literals and several dozen distinct variables.
Using the notoriously challenging Phase Transition dataset we show that, cputime wise, Subsumer clearly outperforms the Django subsumption engine and is competitive with the more sophisticated, state-of-the-art, Resumer2. Furthermore, Subsumer’s memory requirements are only a small fraction of those engines and it can handle arbitrary Prolog clauses whereas Django and Resumer2 can only handle Datalog clauses.
For the entire collection see [Zbl 1213.68040].

MSC:

68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
68N17 Logic programming

Software:

Aleph; Subsumer
PDF BibTeX XML Cite
Full Text: DOI Link