Probabilistic logic over paths. (English) Zbl 1286.03074
Aldini, Alessandro (ed.) et al., Proceedings of the 6th workshop on quantitative aspects of programming languages (QAPL 2008), Budapest, Hungary, March 29–30, 2008. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 220, No. 3, 79-96 (2008).
Summary: We introduce a probabilistic modal logic PPL extending the work of [R. Fagin and J. Y. Halpern, J. Assoc. Comput. Mach. 41, No. 2, 340–367 (1994; Zbl 0806.68098); with N. Megiddo, Inf. Comput. 87, No. 1–2, 78–128 (1990; Zbl 0811.03014)] by allowing arbitrary nesting of a path probabilistic operator and we prove its completeness. We prove that our logic is strictly more expressive than other logics such as the logics cited above. By considering a probabilistic extension of CTL we show that this additional expressive power is really needed in some applications.
For the entire collection see [Zbl 1280.68012].
For the entire collection see [Zbl 1280.68012].
References:
| [1] | Abadi, Martin; Halpern, Joseph Y., Decidability and expressiveness for first-order logics of probability, J. Symbolic Computation, 112, 1, 1-36 (1994) · Zbl 0799.03017 |
| [2] | Alechina, Natasha, Logic with Probabilistic Operators, (Nieuwendijk, A., Proc. of the ACOLADE (1994)), 121-138 · Zbl 1394.68049 |
| [3] | Adnan Aziz, Vigyan Singhal, Felice Balarin, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. It usually works: The temporal logic of stochastic systems. In Proc. of Conference on Computer-Aided Verification; Adnan Aziz, Vigyan Singhal, Felice Balarin, Robert K. Brayton, and Alberto L. Sangiovanni-Vincentelli. It usually works: The temporal logic of stochastic systems. In Proc. of Conference on Computer-Aided Verification |
| [4] | Bacchus, F. Representing and Reasoning with Probabilistic Knowledge, A Logical Approach to Probabilities. Cambridge, Massachusetts: The MIT Press; Bacchus, F. Representing and Reasoning with Probabilistic Knowledge, A Logical Approach to Probabilities. Cambridge, Massachusetts: The MIT Press |
| [5] | Beauquier, Daniele; Rabinovich, Alexander; Slissenko, Anatol, A logic of probability with decidable model checking, J. Log. Comput., 16, 4, 461-487 (2006) · Zbl 1109.03017 |
| [6] | Frank Ciesinski, Marcus Groesser. On probabilistic Computation Tree Logic. in LNCS 2925, Validation of Stochastic Systems, page 147-188; Frank Ciesinski, Marcus Groesser. On probabilistic Computation Tree Logic. in LNCS 2925, Validation of Stochastic Systems, page 147-188 · Zbl 1203.68096 |
| [7] | Cleaveland, Rance; Iyer, S. Purushothaman; Narashima, Murali, Probabilistic Temporal Logic via the Modal Mu-Calculus, Theoretical Computer Science, 342, 2-3, 316-350 (September 2005) · Zbl 1077.68058 |
| [8] | Desharnais, Josee; Edalat, Abbas; Panangaden, Prakash, Bisimulation for labelled Markov processes, (Proceedings of the 12th Symposium on Logic in Computer Science (1997)), 149-158 · Zbl 1096.68103 |
| [9] | Fattorosi-Barnaba, M.; Amati, G., Modal operators with probabilistic interpretations, Studia Logica, 4, 383-393 (1984) · Zbl 0645.03016 |
| [10] | Feldman, Yishai A., A decidable propositional dynamic logic with explicit probabilities, Information and Control, 63, 11-38 (1984) · Zbl 0592.68031 |
| [11] | Feldman, Yishai A.; Harel, David, A probabilistic dynamic logic, Journal of Computer and System Sciences, 28, 193-215 (1984) · Zbl 0537.68036 |
| [12] | Fagin, Ronald; Halpern, Joseph Y., Reasoning about knowledge and probability, Journal of the ACM, 41, 2, 340-367 (1994) · Zbl 0806.68098 |
| [13] | Fagin, Ronald; Halpern, Joseph Y.; Megiddo, Nimrod, A logic for reasoning about probabilities, Information and Computation, 87, 1,2, 78-128 (1990) · Zbl 0811.03014 |
| [14] | Halpern, Joseph Y., An analysis of first order logics of probability, Artificial Intelligence, 46, 311-350 (1990) · Zbl 0723.03007 |
| [15] | Halpern, J., The relationship between knowledge, belief, and certainty, Annals of Mathematics and Artificial Intelligence, 4, 301-322 (1991) · Zbl 0865.03016 |
| [16] | Hanssohn, Hans; Johnsson, Bengt, A logic for reasoning about time and reliability, Formal Aspects of Computing, 6, 5, 512-535 (1994) · Zbl 0820.68113 |
| [17] | Barteld Kooi. Knowledge, chance, and change; Barteld Kooi. Knowledge, chance, and change · Zbl 1185.03014 |
| [18] | Kozen, Dexter, Semantics of probabilistic programs, Journal of Computer and System Sciences, 22, 328-350 (1981) · Zbl 0476.68019 |
| [19] | Kozen, Dexter, A probabilistic PDL, Journal of Computer and System Sciences, 30, 162-178 (1985) · Zbl 0575.03013 |
| [20] | Mateus, P.; Sernadas, A., Weakly complete axiomatization of exogenous quantum propositional logic, Information and Computation, 204 (2006) · Zbl 1116.03021 |
| [21] | Zoran, Ognjanovic, Discrete Linear-time Probabilistic Logics: Completeness, Decidability and Complexity, Journal of Logic Computation, 16, 2, 257-285 (2006) · Zbl 1102.03022 |
| [22] | van Benthem, J., Conditional probability and update logic, Journal of Logic, Language and Information, 12, 409-421 (2003) · Zbl 1031.03045 |
| [23] | W. van der Hoek Modalities for reasoning about knowledge and quantities. Ph.D. thesis, Free University of Amsterdam; W. van der Hoek Modalities for reasoning about knowledge and quantities. Ph.D. thesis, Free University of Amsterdam |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
