Konstantin V. Grekovich¹, Vladimir V. Rybakov¹, Vitaliy V. Rimatskiy¹

¹Siberian Federal University, Krasnoyarsk, Russian Federation

We study intransitive temporal multi-agent logic with agents’ multi-valuations for letters and formulas. In previous wide accepted research the time and knowledge primarily were modeled by Kripke models with structure looking as simply a single time cluster with multi-relations for agents’ accessibility relations. Here we develop this approach and use Kripke models with linear intransitive time and states represented by arbitrary time clusters for agents accessibility multi-relations.

This logic is defined in a semantic way, as a set of formulas, which are true at linear models with multi-valued variables by agents’ and clusters of states. We propose a background for such approach and a technique for computation truth values of formulas. Main result concerns decidability problem. We prove that the resulting logic is decidable and obtain a sort of finite model property.

Konstantin V. Grekovich, Siberian Federal University, Krasnoyarsk, 660041, Russian Federation, propro879@gmail.com

Vladimir V. Rybakov, Dr. Sci. (Phys.-Math.), Prof., Siberian Federal University, Krasnoyarsk, 660041, Svobodniy Ave. 79, Russian Federation, Rybakov@mail.ru

Vitaliy V. Rimatskiy, Cand. Sci. (Phys.-Math), Assoc. Prof., Siberian Federal University, Krasnoyarsk, 660041, Russian Federation, Gemmeny@rambler.ru

Grekovich K. V., Rybakiov V. V., Rimatskiy V.V. Intransitive Temporal Multi-agent Logic with Agents’ Multi-valuations. Decidability. The Bulletin of Irkutsk State University. Series Mathematics, 2025, vol. 51, pp. 141–150. 

https://doi.org/10.26516/1997-7670.2025.51.141

1. Artemov S. Evidence-Based Common Knowledge. Technical Report TR-2004018 CUNY Ph.D. Program in Computer Science, revised version), 2006.
2. Artemov S. Explicit Generic Common Knowledge. Lecture Notes in CS LFCS: Logical Foundations of Computer Science, 2013, pp 16–28.
3. Artemov S. Justification awareness. Journal of Logic and Computation, 2020, vol. 30, no. 8, pp. 1431–1446.
4. 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, 2008, vol. 5028, pp. 32–41.
5. Babenyshev S., Rybakov V. Logic of Discovery and Knowledge: Decision Algorithm. KES (2), Lecture Notes in Computer Science, 2008, vol. 5178, pp. 711–718.
6. Babenyshev S., Rybakov V. Describing Evolutions of Multi-Agent Systems. KES (1) Lecture Notes in Computer Science, 2009, vol. 57, no. 1, pp. 38–45.
7. Baader F., Sattler U. Expressive Number Restrictions in Description Logics. J. Log. Comput, 1999, vol. 9, no. 3, pp. 319–350.
8. Belardinelli F., Lomuscio A. Interactions between Knowledge and Time in a FirstOrder Logic for Multi-Agent Systems, Completeness Results. Journal of Artificial Intelligence Research, 2012, vol. 45, pp. 1–45.
9. Horrocks I., Sattler U. A Description Logic with Transitive and Inverse Roles and Role Hierarchies. Description Logics, 1998.
10. Horrocks I., Giese M., Kharlamov E., Waaler A. Using Semantic Technology to Tame the Data Variety Challenge. IEEE Internet Computing, 2016, vol. 20, no. 6, pp. 62–66.
11. Fagin R., Halpern J. Y., Moses Y., Vardi M. MIT, 1995.
12. Rybakov V.V. Admissibility of logical inference rules. Vol. 136 Studies in Logic and the Foundations of Mathematics. Elsevier Sci. Publ., New-York, Amsterdam, 1997.
13. Rybakov V.V. Non-transitive linear temporal logic and logical knowledge operations, J. Logic and Computation, 2016, vol. 26, no. 3, pp. 945–958.
14. Rybakov V.V. Temporal logic with overlap temporal relations generated by time states themselves. Siberian Mathematical Reports, 2020, vol. 17, pp. 923–932.
15. Rybakov V.V. Multi-agent temporal nontransitive linear logics and the admissibility problem. Algebra and Logic, 2020, no. 59, pp. 87–100. https://doi.org/10.33048/alglog.2020.59.108
16. Rybakov V.V. Branching Time Logics with Multiagent Temporal Accessibility Relations. Siberian Mathematical Journal, 2021, vol. 62, no. 3, pp. 503–510. https://doi.org/10.33048/smzh.2021.62.313
17. Rybakov V. V. Refined common knowledge logics or logics of common information. Archive for Mathematical Logic, 2003, vol. 42, pp. 179–200.
18. Rybakov V. Temporal Multi-Agent’s Logic, Knowledge, Uncertainty, and Plausibility. Agents and Multi-Agent Systems: Technologies and Applications, LNCS, 2021, pp. 2005–2014.
19. Wooldridge M. An Automata-theoretic approach to multi-agent planning. Proceedings of the First European Workshop on Multi-agent Systems (EUMAS), December 2003, Oxford University.