Authors: Ognjanović, Zoran 
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Discrete linear-time probabilistic logics: Completeness, decidability and complexity
Journal: Journal of Logic and Computation
Volume: 16
Issue: 2
First page: 257
Last page: 285
Issue Date: 1-Jan-2006
Rank: M22
ISSN: 0955-792X
DOI: 10.1093/logcom/exi077
We introduce a propositional and a first-order logic for reasoning about discrete linear time and finitely additive probability. The languages of these logics allow formulae that say 'sometime in the future, α holds with probability at least s'. We restrict our study to so-called measurable models. We provide sound and complete infinitary axiomatizations for the logics. Furthermore, in the propositional case decidability is proved by establishing a periodicity argument for ω-sequences extending the decidability proof of standard propositional temporal logic LTL. Complexity issues are examined and a worst-case complexity upper bound is given. Extensions of the presented results and open problems are described in the final part of the paper.
Keywords: Axiomatization | Decidability | Probabilistic logic | Temporal logic
Publisher: Oxford University Press

Show full item record


checked on May 28, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.