Abduction in Annotated Probabilistic Temporal Logic

TitleAbduction in Annotated Probabilistic Temporal Logic
Publication TypeConference Papers
Year of Publication2011
AuthorsMolinaro C, Sliva A, V.S. Subrahmanian
Conference NameTechnical Communications of the 27th International Conference on Logic Programming (ICLP'11)
Date Published2011///
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
ISBN Number978-3-939897-31-6

Annotated Probabilistic Temporal (APT) logic programs are a form of logic programs that allow users to state (or systems to automatically learn)rules of the form ``formula G becomes true K time units after formula F became true with L to U% probability.'' In this paper, we develop a theory of abduction for APT logic programs. Specifically, given an APT logic program Pi, a set of formulas H that can be ``added'' to Pi, and a goal G, is there a subset S of H such that Pi \cup S is consistent and entails the goal G? In this paper, we study the complexity of the Basic APT Abduction Problem (BAAP). We then leverage a geometric characterization of BAAP to suggest a set of pruning strategies when solving BAAP and use these intuitions to develop a sound and complete algorithm.