Multi-agent temporal nontransitive linear logics and the

V. V. Rybakov

Algebra i logika, Tome 59 (2020) no. 1, pp. 123-141.

Résumé

We study an extension of temporal logic, a multi-agent logic on models with nontransitive linear time (which is, in a sense, also an extension of interval logic). The proposed relational models admit lacunas in admissibility relations among agents: information accessible for one agent may be inaccessible for others. A logical language uses temporary operators ‘until’ and ‘next’ (for each of the agents), via which we can introduce modal operations ‘possible’ and ‘necessary.’ The main problem under study for the logic introduced is the recognition problem for admissibility of inference rules. Previously, this problem was dealt with for a logic in which transitivity intervals have a fixed uniform length. Here the uniformity of length of not assumed, and the logic is extended by individual temporal operators for different agents. An algorithm is found which decides the admissibility problem in a given logic, i.e., it recognizes admissible inference rules.

Détail

Keywords: temporal logics, multi-agent logics, problem of admissibility of rules, decision algorithms.
Mots-clés : information

Bibliographie

[1] D. M. Gabbay, I. Hodkinson, M. Reynolds, Temporal logic, v. 1, Oxf. Logic Guides, 28, Mathematical foundations and computational aspects, Clarendon Press, Oxford, 1994 | MR | Zbl

[2] D. M. Gabbay, I. M. Hodkinson, “An axiomatization of the temporal logic with until and since over the real numbers”, J. Log. Comput., 1:2 (1990), 229–259 | DOI | MR | Zbl

[3] D. M. Gabbay, I. Hodkinson, “Temporal logic in the context of databases”, Logic and reality: essays on the legacy of Arthur Prior, Including papers from the Arthur Prior memorial conference (Univ. Canterbury, Christchurch, New Zealand, 1989), ed. B. J. Copeland, Clarendon Press, Oxford, 1996, 69–87 | MR | Zbl

[4] M. Wooldridge, A. Lomuscio, “Multi-agent ${\mathcal VSK}$ logic”, Logics in artificial intelligence, European workshop, JELIA 2000 (Málaga, Spain, September 29-October 2, 2000), Lect. Notes Comput. Sci., 1919, eds. M. Ojeda-Aciego et al., Springer, Berlin, 2000, 300–312 | DOI | MR | Zbl

[5] M. Wooldridge, “An automata theoretic approach to multiagent planning”, Proceedings of the First European Workshop on Multi-agent Systems, EUMAS 2003 (Oxford Univ., December 2003), 15 pp.

[6] M. Wooldridge, M.-P. Huget, M. Fisher, S. Parsons, “Model checking for multiagent systems: The MABLE language and its applications”, Int. J. Artif. Intell. Tools, 15:2 (2006), 195–226 | DOI

[7] F. Belardinelli, A. Lomuscio, “Interactions between knowledge and time in a first-order logic for multi-agent systems: completeness results”, J. Artif. Intell. Res. (JAIR), 45 (2012), 1–45 | DOI | MR | Zbl

[8] S. Babenyshev, V. Rybakov, “Logic of plausibility for discovery in multi-agent environment deciding algorithms”, Knowledge-based intelligent information and engineering systems, KES 2008, Lect. Notes Comput. Sci., 5179, eds. I. Lovrek et al., Springer, Berlin–Heidelberg, 2008, 210–217 | DOI

[9] S. Babenyshev, V. Rybakov, “Decidability of hybrid logic with local common knowledge based on linear temporal logic LTL”, Logic and theory of algorithms, 4th conference on computability in Europe, CiE 2008 (Athens, Greece, June 15-20, 2008), Lect. Notes Comput. Sci., 5028, eds. A. Beckmann et al., Springer, Berlin, 2008, 32–41 | DOI | MR | Zbl

[10] S. Babenyshev, V. Rybakov, “Logic of discovery and knowledge: Decision algorithm”, Knowledge-based intelligent information and engineering systems, KES 2008, Lect. Notes Comput. Sci., 5178, eds. I. Lovrek et al., Springer, Berlin–Heidelberg, 2008, 711–718 | DOI | MR

[11] S. Babenyshev, V. Rybakov, “Describing evolutions of multi-agent systems”, Knowledge-based and intelligent information and engineering systems, KES 2009, Lect. Notes Comput. Sci., 5711, eds. J. D. Velásquez et al., Springer, Berlin–Heidelberg, 2009, 38–45 | DOI | MR

[12] V. V. Rybakov, “Linear temporal logic ${\mathcal{LTL}}_K$ extended by multi-agent logic $K_n$ with interacting agents”, J. Logic Comput., 19:6 (2009), 989–1017 | DOI | MR | Zbl

[13] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995 | MR | Zbl

[14] V. F. Yun, “Vremennaya logika lineinykh po vremeni freimov s aksiomoi induktsii”, Sib. elektron. matem. izv., 6 (2009), 312–325 http://semr.math.nsc.ru/v6/p312-325.pdf | Zbl

[15] J. Hintikka, Knowledge and belief. An introduction to the logic of the two notions, prepared by V. F. Hendricks and J. Symons, reprint of the 1962 original, Texts Philos., 1, King's College Publ., London, 2005 | Zbl

[16] J. F. A. K. van Benthem, The logic of time. A model-theoretic investigation into the varieties of temporal ontology and temporal discourse, Synth. Libr., 156, D. Reidel Publ. Co., Dordrecht a.o., 1983 | MR | Zbl

[17] M. Y. Vardi, “An automata-theoretic approach to linear temporal logic”, Coll. with the British Comp. Soc., 4th higher order workshop (10-14 September 1990, Banff, Alberta, Canada), Workshops in Computing, ed. G. M. Birtwistle, Springer-Verlag, London, 1991, 238–266 http://citeseer.ist.psu.edu/vardi96automatatheoretic.html

[18] M. Y. Vardi, “Reasoning about the past with two-way automata”, Automata, languages and programming, 25th international colloquium, ICALP'98 (Aalborg, Denmark, July 13-17, 1998), Lect. Notes Comput. Sci., 1443, eds. K. G. Larsen et al., Springer, Berlin, 1998, 628–641 | DOI | MR | Zbl

[19] L. L. Maksimova, V. F. Yun, “Silnaya razreshimost i silnaya uznavaemost”, Algebra i logika, 56:5 (2017), 559–581 | Zbl

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

[21] V. V. Rybakov, “Intranzitivnye vremennye mnogoagentnye logiki, informatsiya i znanie, razreshimost”, Sib. matem. zh., 58:5 (2017), 1128–1143 | Zbl

[22] V. V. Rybakov, “Vremennye multiagentnye logiki s multioznachivaniyami”, Sib. matem. zh., 59:4 (2018), 897–911 | Zbl

[23] V. V. Rybakov, “Linear temporal logic with non-transitive time, algorithms for decidability and verification of admissibility”, Larisa Maksimova on implication, interpolation, and definability, Outst. Contrib. Log., 15, ed. S. Odintsov, Springer, Cham, 2018, 219–243 | DOI | MR | Zbl

[24] V. V. Rybakov, “Temporal multi-valued logic with lost worlds in the past”, Sib. elektron. matem. izv., 15 (2018), 436–449 http://semr.math.nsc.ru/v15/p436-449.pdf | MR | Zbl