Complexity and expressive power of logic programming

By Evgeny Dantsin, Thomas Eiter, Georg Gottlob, Andrei Voronkov. 1997

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Natural Language Processing

Citations in the corpus

Neural Logic Machines (2019, background): “the number of logic rules to be learned (Dantsin et al., 2001; Lin et al., 2014; Evans & Grefenstette, 2018).”
TriAL (2018, background): “Note that this also makes a strong argument to prefer the use of the algebra in place of the Datalog programs of Section 4, since the latter have intrinsically high evaluation complexity (i.e., EXPTIME [21]).”
Answer Set Solving in Practice (2012, unknown): “Constraint Answer Set Programming [13] E.”
ASP-Core-2 Input Language Format (2019, background): “Arbitrary usage of disjunction in programs might cause a shift in complexity towards F −ΣP 2 [3].”
A general datalog-based framework for tractable query answering over ontologies (2009, methodology): “Then,D∪Σ |= Q iffD∪S ′ |= q, where the latter can be decided in linear time [38].”
Causes and explanations in the structural-model approach: Tractable cases (2002, background): “For example, complexity results on answer set programming [ 5 ] have guided the development of efficient solvers such as DLV [25].”
Potassco: The Potsdam Answer Set Solving Collection (2011, unknown): “Meanwhile, ASP has been used in many application areas, among them, product conﬁguration [96], decision support for NASA shuttle controllers [86], composition of Renaissance music [10], synthesis of multiprocessor systems [71], reasoning tools in systems biology [30,55], (industrial) team-building…”
ELP: Tractable Rules for OWL 2 (2008, background): “Yet, this formalism can still capture all Datalog programs, and therefore satisfiability checking remains ET hard (Dantsin et al. 2001).”
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints (2008, background): “ﬁxed) queries Qand for ﬁxed Σ follows from the fact that ground atom inference from a ﬁxed fully guarded Datalog program over variable databases is ptime-hard. In fact, in the proof of Theorem 4.4 in [37] it is shown that fact inference from a single-rule Datalog program whose body has a guard atom ”
MulVAL: A Logic-based Network Security Analyzer (2005, background): “The complexity of a Datalog program with well-founded negation is polynomial in the size of input [6].”
Minimal-change integrity maintenance using tuple deletions (2002, background): “This is because the classes of logic programs used are Πp2-complete [26].”
Logic Programming (2001, unknown): “Other histories and surveys that cover some of these topics and give other perspectives include [Apt and Bol, 1994; Brewka et al., 2011; Bry et al. 2007; Ceri et al., 1990; Cohen, 1988; Colmerauer and Roussel, 1996; Costantini, 2002; Dantsin et al., 1997; Eiter et al., 2009; Elcock, 1990; van Emden,”