Eleventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1996)

Paper: On the Complexity of Abduction (at LICS 1996)

Authors: Victor W. Marek Anil Nerode Jeffrey B. Remmel


In this paper we consider the complexity of the existence problem for explanations and for minimal explanations for abductive frameworks based on finite predicate programs. We find that although, in general, the problem is very complex, there are classes of frameworks for which the problem is much simpler.


    author = 	 {Victor W. Marek and Anil Nerode and Jeffrey B. Remmel},
    title = 	 {On the Complexity of Abduction},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {513-522},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}