Name
Abstract | ||
|---|---|---|
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 e ffi ciently 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 (approximate to 1000 lines in Prolog) but e ffi cient 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 e ffi ciently 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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.4230/LIPIcs.ICLP.2010.172 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Theta-subsumption,Prolog,Inductive Logic Programming | Inductive logic programming,Computational logic,Bottleneck,Programming language,Computer science,Constraint programming,Imperative programming,Theoretical computer science,Prolog,Logic programming,Datalog | Conference |
Volume | ISSN | Citations |
7 | 1868-8969 | 4 |
PageRank | References | Authors |
0.45 | 1 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jose Santos | 1 | 11 | 1.37 |
| Stephen Muggleton | 2 | 3915 | 619.54 |