The satisfiability problem in linear multi-agent knowledge logic based on $\mathbb{N}$

N. A. Protsenko ; V. V. Rybakov

The Bulletin of Irkutsk State University. Series Mathematics, Tome 49 (2024), pp. 124-134

Résumé

In this paper we explore the linear logic of multi-agent knowledge using multivalued models. The logic of the language contains the unary operators $K_{j}$ — $j$ — the agent knows, $ULK_{G}$ — unstable local knowledge, $E_{G}$ — stable local knowledge in the group, and the binary logical operator $AP_{G}$ - the majority opinion. We will show some examples that demonstrate the diversity of this language and its capabilities. Technically we prove decidability of satisfiability problem in the resulting models for our multi-agent logic, develop verification technique and provide some examples.

Détail

Keywords: modal logic, temporal logic, common knowledge, deciding algorithms, multi-agent logic.

Bibliographie

[1] Babenyshev S., Rybakov V., “Logic of Plausibility for Discovery in Multi-agent Environment Deciding Algorithms”, KES (3), Lecture Notes in Computer Science, 5179, 2008, 210–217 | DOI | MR

[2] Babenyshev S., Rybakov V., “Decidability of Hybrid Logic with Local Common Knowledge Based on Linear Temporal Logic LTL”, CiE 2008, Lecture Notes in Computer Science, 5028, 2008, 32–41 | DOI | MR | Zbl

[3] Barwise J., “Three views of common knowledge”, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, TARK '88, 1988, 365–379 | DOI | MR | Zbl

[4] Belardinelli F., Lomuscio A., “Interactions between Knowledge and Time in a First-Order Logic for Multi-Agent Systems: Completeness Results”, Journal of Artificial Intelligence Research, 45 (2012), 1–45 | DOI | MR | Zbl

[5] Ding Y., Liu J., Wang Y., “Someone knows that local reasoning on hypergraphs is a weakly aggregative modal logic”, Synthese, 201 (2023), 46 | DOI | MR

[6] Fagin R., Halpern J., Vardi M., “A Model-Theoretic Analysis of Knowledge: Preliminary Report”, IEEE Annual Symposium on Foundations of Computer Science, 1984, 268–278 | DOI | MR

[7] Fagin R., Halpern J., Moses Y., Vardi M., Reasoning About Knowledge, The MIT Press, Cambridge, Massachusetts, 1995, 477 pp. | MR

[8] McLean D., Rybakov V., “Multi-Agent Temporary Logic $TS4^{U_{K_n}}$ Based at Non-linear Timeand Imitating Uncertainty via Agents Interaction”, Artificial Intelligence and Soft Computing, 2013, 375–384 | DOI

[9] Moor M.A., Rybakov V.V., “Many-valued multi-modal logics, satisfiability problem”, Siberian Electronic Mathematical Reports, 15 (2018), 829–838 | DOI | MR | Zbl

[10] Pnueli A., “The temporal logic of programs”, Proceedings of the 18th Annual Symposium on Foundations of Computer Science, FOCS, 1977, 46–57 | DOI | MR

[11] Prior A., Time and modality, Oxford University Press, Oxford, 1957, 148 pp. | Zbl

[12] Protsenko N.A., Rybakov V.V., Rimatskiy V.V., “Satisfiability Problem in Interval FP-logic”, The Bulletin of Irkutsk State University. Series Mathematics, 44 (2023), 98–107 | DOI | MR

[13] Rybakov V., Babenyshev S., “Multi-agent logic with distances based on linear temporal frames”, Artifical Intelligence and Soft Computing, Conference Proceedings, Springer, 2010, 337–344

[14] Rybakov V.V., “Non-transitive linear temporal logic and logical knowledge operations”, J. Logic and Computation, 26:3 (2016), 945–958 | DOI | MR | Zbl

[15] Rybakov V.V., “Multiagent Temporal Logics with Multivaluations”, Siberian Mathematical Journal, 59:4 (2018), 710–720 | DOI | MR | Zbl

[16] Rybakov V., “Refined common knowledge logics or logics of common information”, Arch. Math. Logic, 42 (2003), 179–200 | DOI | MR | Zbl

[17] Wooldridge M., Lomuscio A., “Multi-Agent VSK Logic”, Proceedings of the Seventh European Workshop on Logics in Artificial Intelligence, JELIAI-2000, Springer-Verlag, 2000 | MR