First-Order Linear-time Epistemic Logic with Group Knowledge: An Axiomatisation of the Monodic Fragment

• Autorzy: Belardinelli F. , Lomuscio A.
• Języki publikacji: EN

Abstrakty

EN

We investigate quantified interpreted systems, a computationally grounded semantics for a first-order temporal epistemic logic on linear time. We report a completeness result for themonodic fragment of a language that includes LTL modalities as well as distributed and common knowledge. We exemplify possible uses of the formalismby analysingmessage passing systems, a typical framework for distributed systems, in a first-order setting.

Słowa kluczowe

EN

First-order Modal Logic; temporal logic; epistemic logics; multi-agent systems; completeness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 106, nr 2-4
• Strony: 175--190
• Opis fizyczny: Bibliogr. 31 poz., tab.

Twórcy

autor

Belardinelli F.

autor

Lomuscio A.

• Department of Computing, Imperial College London, UK,

Bibliografia

• [1] Belardinelli, F., Lomuscio, A.: A Complete First-Order Logic of Knowledge and Time, KR (G. Brewka, J. Lang, Eds.), AAAI Press, 2008, ISBN 978-1-57735-384-3.
• [2] Belardinelli, F., Lomuscio, A.: Quantified epistemic logics for reasoning about knowledge in multi-agent systems, Artificial Intelligence, 173(9-10), 2009, 982-1013.
• [3] Blackburn, P., van Benthem, J., Wolter, F., Eds.: Handbook of Modal Logic, Elsevier, 2007.
• [4] Cohen, P., Levesque, H.: CommunicativeActions for Artificial Agents, Proceedings of the First International Conference on Multi-Agent Systems (ICMAS'95), AAAI Press, 1995.
• [5] Fagin, R., Halpern, J. Y., Moses, Y., Vardi, M. Y.: Reasoning about Knowledge, MIT Press, Cambridge, 1995, ISBN 0-262-06162-7.
• [6] Gabbay, D., Kurucz, A., Wolter, F., Zakharyaschev, M.: Many-Dimensional Modal Logics: Theory and Applications, vol. 148 of Studies in Logic, Elsevier, 2003, ISBN 0-444-50826-0.
• [7] Gammie, P., van der Meyden, R.: MCK: Model Checking the Logic of Knowledge, Proceedings of 16th International Conference on Computer Aided Verification (CAV'04), 3114, Springer-Verlag, 2004.
• [8] Halpern, J., van der Meyden, R., Vardi, M.: Complete Axiomatizations for Reasoning about Knowledge and Time, SIAM J. Comput., 33(3), 2004, 674-703.
• [9] Halpern, J., Moses, Y.: Knowledge and common knowledge in a distributed environment, Journal of the ACM, 37(3), 1990, 549-587, A preliminary version appeared in Proc. 3rd ACM Symposium on Principles of Distributed Computing, 1984.
• [10] Halpern, J., Moses, Y.: A Guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence, 54, 1992, 319-379.
• [11] Halpern, J. Y., Vardi,M. Y.: The complexity of reasoning about knowledge and time 1: lower bounds, Journal of Computer and System Sciences, 38(1), 1989, 195-237.
• [12] Hodkinson, I.: Monodic Packed Fragment with Equality is Decidable, Studia Logica, 72, 2002, 185-197.
• [13] Hodkinson, I.: Complexity of monodic guarded fragments over linear and real time, Annals of Pure and Applied Logic, 138, 2006, 94-125.
• [14] Hodkinson, I. M., Kontchakov, R., Kurucz, A., Wolter, F., Zakharyaschev, M.: On the Computational Complexity of Decidable Fragments of First-Order Linear Temporal Logics., TIME, IEEE Computer Society, 2003, ISBN 0-7695-1912-1.
• [15] Hodkinson, I. M., Wolter, F., Zakharyaschev,M.: Decidable fragment of first-order temporal logics, Annals of Pure and Applied Logic, 106(1-3), 2000, 85-134.
• [16] Hodkinson, I. M., Wolter, F., Zakharyaschev, M.: Decidable and Undecidable Fragments of First-Order Branching Temporal Logics., LICS, IEEE Computer Society, 2002, ISBN 0-7695-1483-9.
• [17] Hoek, W., Meyer, J., Treur, J.: Formal Semantics of Temporal Epistemic Reflection, Logic Program Synthesis and Transformation - Meta-Programming in Logic, 4th International Workshops (LOPSTR'94 and META'94), 883, Springer Verlag, Pisa, 1994.
• [18] Lamport, L.: Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, 21(7), 1978, 558-565, ISSN 0001-0782.
• [19] Meyden, R.: Axioms for Knowledge and Time in Distributed Systems with Perfect Recall, Proceedings, Ninth Annual IEEE Symposium on Logic in Computer Science, IEEE Computer Society Press, Paris, France, 1994.
• [20] Meyer, J.-J. C., Hoek, W.: Epistemic Logic for AI and Computer Science, vol. 41 of Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 1995.
• [21] Parikh, R., Ramanujam, R.: Distributed Processes and the Logic of Knowledge., Logic of Programs (R. Parikh, Ed.), 193, Springer, 1985, ISBN 3-540-15648-8.
• [22] Raimondi, F., Lomuscio, A.: Automatic verification of multi-agent systems by model checking via ordered binary decision diagrams, J. Applied Logic, 5(2), 2007, 235-251.
• [23] Rao, A., Georgeff,M.: Deliberation and its Role in the Formation of Intentions, Proceedings of the 7th Conference on Uncertainty in Artificial Intelligence (B. D. D'Ambrosio, P. Smets, P. Bonissone, Eds.), Morgan Kaufmann Publishers, San Mateo, CA, USA, 1991, ISBN 1-55860-203-8.
• [24] Reynolds, M.: Axiomatising first-order temporal logic: until and since over linear time., Studia Logica, 57(2/3), 1996, 279-302.
• [25] Sturm, H., Wolter, F., Zakharyaschev, M.: Monodic Epistemic Predicate Logic., JELIA (M. Ojeda-Aciego, I. P. de Guzm´an, G. Brewka, L. M. Pereira, Eds.), 1919, Springer, 2000, ISBN 3-540-41131-3.
• [26] Sturm, H., Wolter, F., Zakharyaschev, M.: Common Knowledge and Quantification, Economic Theory, 19, 2002, 157-186.
• [27] Wolter, F.: First Order Common Knowledge Logics., Studia Logica, 65(2), 2000, 249-271.
• [28] Wolter, F., Zakharyaschev, M.: Decidable Fragments of First-Order Modal Logics., Journal of Symbolic Logic, 66(3), 2001, 1415-1438.
• [29] Wolter, F., Zakharyaschev,M.: Axiomatizing the monodic fragment of first-order temporal logic., Annals of Pure and Applies Logic, 118(1-2), 2002, 133-145.
• [30] Wooldridge, M.: Computationally grounded theories of agency, in: Proceedings of ICMAS, International Conference of Multi-Agent Systems (E. Durfee, Ed.), IEEE Press, 2000, 13-22.
• [31] Wooldridge,M.: Reasoning about Rational Agents, MIT Press, 2000.