Imperial College London
Alternate

DrKrysiaBroda

Faculty of Engineering, Department of Computing

Honorary Senior Lecturer
 
 
 
//

Contact

 

k.broda Website

 
 
//

Location

 

Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@article{Law:2018:10.1016/j.artint.2018.03.005,
author = {Law, M and Russo, AM and Broda, K},
doi = {10.1016/j.artint.2018.03.005},
journal = {Artificial Intelligence},
pages = {110--146},
title = {The complexity and generality of learning answer set programs},
url = {http://dx.doi.org/10.1016/j.artint.2018.03.005},
volume = {259},
year = {2018}
}
Download

RIS format (EndNote, RefMan)

TY  - JOUR
AB  - Traditionally most of the work in the field of Inductive Logic Programming (ILP) has addressed the problem of learning Prolog programs. On the other hand, Answer Set Programming is increasingly being used as a powerful language for knowledge representation and reasoning, and is also gaining increasing attention in industry. Consequently, the research activity in ILP has widened to the area of Answer Set Programming, witnessing the proposal of several new learning frameworks that have extended ILP to learning answer set programs. In this paper, we investigate the theoretical properties of these existing frameworks for learning programs under the answer set semantics. Specifically, we present a detailed analysis of the computational complexity of each of these frameworks with respect to the two decision problems of deciding whether a hypothesis is a solution of a learning task and deciding whether a learning task has any solutions. We introduce a new notion of generality of a learning framework, which enables us to define a framework to be more general than another in terms of being able to distinguish one ASP hypothesis solution from a set of incorrect ASP programs. Based on this notion, we formally prove a generality relation over the set of existing frameworks for learning programs under answer set semantics. In particular, we show that our recently proposed framework, Context-dependent Learning from Ordered Answer Sets, is more general than brave induction, induction of stable models, and cautious induction, and maintains the same complexity as cautious induction, which has the highest complexity of these frameworks.
AU  - Law,M
AU  - Russo,AM
AU  - Broda,K
DO  - 10.1016/j.artint.2018.03.005
EP  - 146
PY  - 2018///
SN  - 1872-7921
SP  - 110
TI  - The complexity and generality of learning answer set programs
T2  - Artificial Intelligence
UR  - http://dx.doi.org/10.1016/j.artint.2018.03.005
UR  - http://hdl.handle.net/10044/1/58406
VL  - 259
ER  -
Download