×

zbMATH — the first resource for mathematics

A guide to completeness and complexity for modal logics of knowledge and belief. (English) Zbl 0762.68029
Summary: We review and re-examine possible-worlds semantics for propositional logics of knowledge and belief with three particular points of emphasis:
(1) we show how general techniques for finding decision procedures and complete axiomatizations apply to models for knowledge and belief,
(2) we show how sensitive the difficulty of the decision procedure is to such issues as the choice of modal operators and the axiom system, and
(3) we discuss how notions of common knowledge and distributed knowledge among a group of agents fit into the possible-worlds framework.
As far as complexity is concerned, we show, among other results, that while the problem of deciding satisfiability of an \(S5\) formula with one agent is \(NP\)-complete, the problem for many agents in PSPACE-complete. Adding a distributed knowledge operator does not change the complexity, but once a common knowledge operator is added to the language, the problem becomes complete for exponential time.

MSC:
68Q25 Analysis of algorithms and problem complexity
68T30 Knowledge representation
03B45 Modal logic (including the logic of norms)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barringer, H.; Gough, G.D., Mechanization of temporal logic, part 1: techniques, (1988), University of Manchester, Draft
[2] Beth, E.W., ()
[3] Chandra, A.K.; Kozen, D.; Stockmeyer, L.J., Alternation, J. ACM, 28, 114-133, (1981) · Zbl 0473.68043
[4] Chellas, B.F., ()
[5] Clark, H.H.; Marshall, C.R., Definite reference and mutual knowledge, ()
[6] Cook, S.A., The complexity of theorem proving procedures, (), 151-158 · Zbl 0363.68125
[7] Cresswell, M.J., ()
[8] Dwork, C.; Moses, Y., Knowledge and common knowledge in a Byzantine environment: crash failures, Inf. comput., 88, 2, 156-186, (1990) · Zbl 0705.68019
[9] Emerson, E.A.; Halpern, J.Y., Decision procedures and expressiveness in the temporal logic of branching time, J. comput. syst. sci., 30, 1, 1-24, (1985) · Zbl 0559.68051
[10] Fagin, R.; Halpern, J.Y., Belief, awareness, and limited reasoning, Artif. intell., 34, 39-76, (1988) · Zbl 0634.03013
[11] Fagin, R.; Halpern, J.Y.; Vardi, M.Y.; Fagin, R.; Halpern, J.Y.; Vardi, M.Y., What can machines know? on the properties of knowledge in distributed systems, (), IBM research report RJ 6250, J. ACM, 428-434, (1992), to appear in · Zbl 0799.68179
[12] Fagin, R.; Vardi, M.Y., Knowledge and implicit knowledge in a distributed environment: preliminary report, (), 187-206
[13] Fischer, M.J.; Immerman, N., Interpreting logics of knowledge in propositional dynamic logic with converse, Inf. process. lett., 25, 3, 175-182, (1987) · Zbl 0634.03012
[14] Fischer, M.J.; Ladner, R.E., Propositional dynamic logic of regular programs, J. comput. syst. sci., 18, 2, 194-211, (1979) · Zbl 0408.03014
[15] Gettier, E., Is justified true belief knowledge?, Analysis, 23, 121-123, (1963)
[16] Goldblatt, R., (), CSLI Lecture Notes 7
[17] Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. comput., 18, 1, 186-208, (1989) · Zbl 0677.68062
[18] Halpern, J.Y., Using reasoning about knowledge to analyze distributed systems, (), 37-68
[19] Halpern, J.Y.; Moses, Y., A guide to the modal logics of knowledge and belief, (), 480-490
[20] Halpern, J.Y.; Moses, Y., Knowledge and common knowledge in a distributed environment, (), 37, 3, 549-587, (1990), early version in · Zbl 0699.68115
[21] Halpern, J.Y.; Moses, Y.; Tuttle, M.R., A knowledge-based analysis of zero knowledge, (), 132-147
[22] Halpern, J.Y.; Vardi, M.Y., The complexity of reasoning about knowledge and time, I: lower bounds, J. comput. syst. sci., 38, 1, 195-237, (1989) · Zbl 0672.03015
[23] Hintikka, J., Modalities and quantification, Theoria, 27, 61, 119-128, (1961)
[24] Hintikka, J., ()
[25] Hintikka, J., Impossible possible worlds vindicated, J. philos. logic, 4, 475-484, (1975) · Zbl 0334.02003
[26] Hopcroft, J.E.; Ullman, J.D., ()
[27] Hughes, G.E.; Cresswell, M.J., ()
[28] Hughes, G.E.; Cresswell, M.J., ()
[29] Imielinski, T., Relative knowledge in a distributed database, (), 197-209
[30] Kanger, S., On the characterization of modalities, Theoria, 23, 152-155, (1957) · Zbl 0087.25201
[31] Kanger, S., Provability in logic, (1957), Stockholm Studies in Philosophy I
[32] Kaplan, D., Review of “a semantical analysis of modal logic I: normal modal propositional calculi”, J. symbolic logic, 31, 120-122, (1966)
[33] Kozen, D.; Parikh, R., An elementary proof of the completeness of PDL, Theor. comput. sci., 14, 1, 113-118, (1981) · Zbl 0451.03006
[34] Kripke, S., A semantical analysis of modal logic I: normal modal propositional calculi, Z. math. logik grundl. math., J. symbolic logic, 24, 323-96, (1959), Announced in · Zbl 0118.01305
[35] Ladner, R.E., The computational complexity of provability in systems of modal propositional logic, SIAM J. comput., 6, 3, 467-480, (1977) · Zbl 0373.02025
[36] Lehmann, D.J., Knowledge, common knowledge, and related puzzles, (), 62-67
[37] Lenzen, W., Recent work in epistemic logic, Acta philos. fenn., 30, 1-219, (1978) · Zbl 0397.03002
[38] Levesque, H.J., Foundations of a functional approach to knowledge representation, Artif. intell., 23, 155-212, (1984) · Zbl 0548.68090
[39] Levesque, H.J., A logic of implicit and explicit belief, (), 198-202
[40] Levesque, H.J., All I know: A study in autoepistemic logic, Artif. intell., 42, 3, 263-309, (1990) · Zbl 0724.03019
[41] Makinson, D., On some completeness theorems in modal logic, Z. math. logik grundl. math., 12, 379-384, (1966) · Zbl 0295.02014
[42] McArthur, G.L., Reasoning about knowledge and belief: a survey, Comput. intell., 4, 223-243, (1988)
[43] McCarthy, J.; Sato, M.; Hayashi, T.; Igarishi, S., On the model theory of knowledge, ()
[44] McCarthy, J.M.; Hayes, P.J., Some philosophical problems from the standpoint of artificial intelligence, (), 463-502 · Zbl 0226.68044
[45] Merritt, M.J., Cryptographic protocols, ()
[46] Milgrom, P., An axiomatic characterization of common knowledge, Econometrica, 49, 1, 219-222, (1981) · Zbl 0453.90028
[47] Moore, R.C., A formal theory of knowledge and action, (), 319-358
[48] Moses, Y., Resource-bounded knowledge, (), 261-276
[49] Moses, Y.; Tuttle, M.R., Programming simultaneous actions using common knowledge, Algorithmica, 3, 121-169, (1988) · Zbl 0646.68031
[50] Pratt, V.R., Models of program logics, (), 115-122
[51] Rantala, V., Impossible worlds semantics and logical omniscience, Acta philos. fenn., 35, 18-24, (1982) · Zbl 0519.03002
[52] Reiter, R., On integrity constraints, (), 97-112
[53] Rosenschein, S.J., Formal theories of AI in knowledge and robotics, New generation comput., 3, 345-357, (1985) · Zbl 0596.68061
[54] Sato, M., A study of Kripke-style methods for some modal logics by Gentzen’s sequential method, Publ. res. inst. math. sci. Kyoto univ., 13, 2, (1977) · Zbl 0405.03013
[55] Smullyan, R., ()
[56] Stockmeyer, L.J.; Meyer, A.R., Word problems requiring exponential time: preliminary report, (), 1-9 · Zbl 0359.68050
[57] van Benthem, J.F.A.K., ()
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.