Annotated probabilistic temporal logic
Authors:
Open Access
- 27 January 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 12 (2) , 1-44
Abstract
The semantics of most logics of time and probability is given via a probability distribution over threads , where a thread is a structure specifying what will be true at different points in time (in the future). When assessing the probabilities of statements such as “Event a will occur within 5 units of time of event b ,” there are many different semantics possible, even when assessing the truth of this statement within a single thread. We introduce the syntax of annotated probabilistic temporal (APT) logic programs and axiomatically introduce the key notion of a frequency function (for the first time) to capture different types of intrathread reasoning, and then provide a semantics for intrathread and interthread reasoning in APT logic programs parameterized by such frequency functions. We develop a comprehensive set of complexity results for consistency checking and entailment in APT logic programs, together with sound and complete algorithms to check consistency and entailment. The basic algorithms use linear programming, but we then show how to substantially and correctly reduce the sizes of these linear programs to yield better computational properties. We describe a real world application we are developing using APT logic programs.Keywords
Funding Information
- Army Research Office (W911NF0910206)
- Office of Naval Research (N000140910685)
- Air Force Office of Scientific Research (FA95500610405)
This publication has 24 references indexed in Scilit:
- Computing most probable worlds of action probabilistic logic programs: scalable estimation for 1030,000 worldsAnnals of Mathematics and Artificial Intelligence, 2007
- Heterogeneous temporal probabilistic agentsACM Transactions on Computational Logic, 2006
- Probabilistic temporal logics via the modal mu-calculusTheoretical Computer Science, 2005
- A parametric approach to deductive databases with uncertaintyIEEE Transactions on Knowledge and Data Engineering, 2001
- A logic for reasoning about time and reliabilityFormal Aspects of Computing, 1994
- Reasoning about knowledge and probabilityJournal of the ACM, 1994
- Theory of generalized annotated logic programming and its applications**A preliminary report on this research has appeared in [34].The Journal of Logic Programming, 1992
- Probabilistic propositional temporal logicsInformation and Control, 1986
- Proving Liveness Properties of Concurrent ProgramsACM Transactions on Programming Languages and Systems, 1982
- Reasoning with time and chanceInformation and Control, 1982