{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T03:14:08Z","timestamp":1775013248323,"version":"3.50.1"},"reference-count":36,"publisher":"Pleiades Publishing Ltd","issue":"5","license":[{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T00:00:00Z","timestamp":1251763200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Program Comput Soft"],"published-print":{"date-parts":[[2009,9]]},"DOI":"10.1134\/s036176880905003x","type":"journal-article","created":{"date-parts":[[2009,9,19]],"date-time":"2009-09-19T16:34:44Z","timestamp":1253378084000},"page":"266-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Systems of agents controlled by logical programs: Complexity of verification"],"prefix":"10.1134","volume":"35","author":[{"given":"M. K.","family":"Valiev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. I.","family":"Dekhtyar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. Ya.","family":"Dikovsky","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"137","published-online":{"date-parts":[[2009,9,20]]},"reference":[{"key":"6040_CR1","first-page":"18","volume-title":"Trudy konferentsii, posvyashchennoi 90-letiyu so dnya rozhdeniya A.A. Lyapunova","author":"M.K. Valiev","year":"2001","unstructured":"Valiev, M.K., Dekhtyar, M.I., and Dikovsky, A.Ya., On the Complexity of Behavior of Systems of Interacting Agents, Trudy konferentsii, posvyashchennoi 90-letiyu so dnya rozhdeniya A.A. Lyapunova (Proc. of the Conf. Dedicated to the 90th Birthday of A.A. Lyapunov), Novosibirsk: Nauka, 2001, pp. 18\u201328."},{"issue":"1","key":"6040_CR2","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1016\/S0304-3975(02)00445-0","volume":"303","author":"M. Dekhtyar","year":"2003","unstructured":"Dekhtyar, M., Dikovsky, A., and Valiev, M., On Feasible Cases of Checking Multi-Agent Systems Behavior, Theor. Comput. Sci., 2003, vol. 303, no. 1, pp. 63\u201381.","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"6040_CR3","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/j.apal.2005.12.003","volume":"141","author":"M.K. Dekhtyar","year":"2006","unstructured":"Dekhtyar, M.K., Dikovsky, A.Ja, and Valiev, M.K., On Complexity of Verification of Interacting Agents\u2019 Behavior, Ann. Pure Appl. Logic, 2006, vol. 141, no. 3, pp. 336\u2013362.","journal-title":"Ann. Pure Appl. Logic"},{"key":"6040_CR4","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/BF01211631","volume":"7","author":"H. Barringer","year":"1995","unstructured":"Barringer, H., Fisher, M., Gabbay, D., Gough, G., and Owens, R., METATEM: An Introduction, in Formal Aspects of Computing, 1995, vol. 7, pp. 533\u2013549.","journal-title":"Formal Aspects of Computing"},{"key":"6040_CR5","unstructured":"Georgeff, M. and Lansky, A., Reactive Reasoning and Planning, Proc. of the Conf. of the American Association of Artificial Intelligence, Seattle, 1987, pp. 677\u2013682."},{"key":"6040_CR6","first-page":"887","volume-title":"Handbook of Knowledge Representation","author":"W. van der Hoek","year":"2008","unstructured":"van der Hoek, W. and Wooldridge, M., Multi-Agent Systems, in Handbook of Knowledge Representation, van Harmelen, F., Lifschitz, V., and Porter, B., Eds., Amsterdam: Elsevier, 2008, pp. 887\u2013928."},{"key":"6040_CR7","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/4074.001.0001","volume-title":"Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems","author":"R. Reiter","year":"2001","unstructured":"Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, Cambridge: MIT, 2001."},{"key":"6040_CR8","doi-asserted-by":"crossref","unstructured":"Shoham, Y., Agent Oriented Programming, Artif. Intell., 1993, no. 60, pp. 51\u201392.","DOI":"10.1016\/0004-3702(93)90034-9"},{"key":"6040_CR9","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3487.001.0001","volume-title":"Heterogeneous Agent Systems","author":"V.S. Subrahmanian","year":"2000","unstructured":"Subrahmanian, V.S., Bonatti, P., Dix, J., et. al., Heterogeneous Agent Systems, Cambridge: MIT, 2000."},{"key":"6040_CR10","volume-title":"Ot mnogoagentnykh system k intellektual\u2019nym organizatsiyam","author":"V.B. Tarasov","year":"2002","unstructured":"Tarasov, V.B., Ot mnogoagentnykh system k intellektual\u2019nym organizatsiyam (From Multiagent Systems to Intellectual Organizations), Moscow: Editorial URSS, 2002."},{"key":"6040_CR11","doi-asserted-by":"crossref","unstructured":"Araragi, T., Attie, P., Keidar, I., Kogure, K., Luchangco, V., Lynch, N., and Mano, K., On Formal Modeling of Agent Computations, NASA Workshop on Formal Approaches to Agent-Based Systems, 2000.","DOI":"10.1007\/3-540-45484-5_4"},{"key":"6040_CR12","unstructured":"Benerecetti, M., Guinchiglia, F., and Serafini, L., Model Checking Multiagent Systems, Technical Report no. 9708-07, Instituto Trentino di Cultura, 1998."},{"key":"6040_CR13","doi-asserted-by":"crossref","unstructured":"Bordini, R.H., Fisher, M., Pardavila, C., and Woold-ridge, M., Model Checking AgentSpeak, Proc. of the Second Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS-03), Melbourne, 2003.","DOI":"10.1145\/860575.860641"},{"key":"6040_CR14","series-title":"Lecture Notes in AI","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45448-9_9","volume-title":"Intelligent Agents VIII","author":"M. Wooldridge","year":"2002","unstructured":"Wooldridge, M. and Dunne, P.E., The Computational Complexity of Agent Verification, in Intelligent Agents VIII, Meyer, J.J. and Tambe, M., Eds., Lecture Notes in AI, vol. 2333, Berlin: Springer, 2002."},{"issue":"2","key":"6040_CR15","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1142\/S0218213006002631","volume":"5","author":"M. Wooldridge","year":"2006","unstructured":"Wooldridge, M., Huget, M.P., Fisher, M., and Parsons, S., Model Checking Multi-Agent Systems: The MABLE Language and Its Applications, Int. J. Artif. Intell. Tools, 2006, vol. 5, no. 2, pp. 195\u2013225. (Preliminary version: Wooldridge, M., Huget, M.P., Fisher, M., and Parsons, S., Model Checking Multiagent Systems with MABLE, Proc. of the First Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS-02), Bologna, 2002.","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"6040_CR16","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning about Knowledge","author":"R. Fagin","year":"1995","unstructured":"Fagin, R., Halpern, J.Y., Moses, Y., and Vardy, M.Y., Reasoning about Knowledge, Cambridge: MIT, 1995."},{"key":"6040_CR17","unstructured":"Eiter, T. and Subrahmanian, V.S., Heterogeneous Active Agents. III: Polynomially Implementable Agents, Tech. Rep. INFSYS RR-1843-99-07, Inst. f\u00fcr Informationssysteme, Technische Universit\u00e4t Wien, A-10-40,Vienna, 1999."},{"key":"6040_CR18","doi-asserted-by":"crossref","unstructured":"Clarke, E.M. and Emerson, E.A., Design and Synthesis of Synchronization Skeletons Using Branching Time Temporal Logic, Proc. of Workshop on Logics of Programs, Lecture Notes in Computer Science, 1981, no. 181, pp. 52\u201371.","DOI":"10.1007\/BFb0025774"},{"key":"6040_CR19","unstructured":"Vardi, M. and Wolper, P., An Automata-Theoretic Approach to Automatic Program Verification, Proc. of the IEEE Symposium on Logic in Computer Science, 1986, pp. 332\u2013344."},{"key":"6040_CR20","doi-asserted-by":"crossref","unstructured":"Queille, J.P. and Sifakis, J., Specification and Verification of Concurrent Programs in CESAR, Proc. of the 5th Int. Symposium on Programming, Lecture Notes in Computer Science, 1982, no. 137, pp. 195\u2013220.","DOI":"10.1007\/3-540-11494-7_22"},{"issue":"3","key":"6040_CR21","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1145\/3828.3837","volume":"32","author":"A.P. Sistla","year":"1985","unstructured":"Sistla, A.P. and Clarke, E.M., The Complexity of Propositional Linear Temporal Logic, J. Assoc. Comput. Mach., 1985, vol. 32, no. 3, pp. 733\u2013749.","journal-title":"J. Assoc. Comput. Mach."},{"key":"6040_CR22","volume-title":"Handbook of Theoretical Computer Science","author":"E.A. Emerson","year":"1990","unstructured":"Emerson, E.A., Temporal and Modal Logic, in Handbook of Theoretical Computer Science, Leeuwen, J., Ed., Amsterdam: Elsevier, 1990."},{"key":"6040_CR23","first-page":"185","volume-title":"Descriptive Complexity and Finite Models, Proc. of the DIMACS Workshop","author":"E.A. Emerson","year":"1996","unstructured":"Emerson, E.A., Model Checking and the Mu-Calculus, in Descriptive Complexity and Finite Models, Proc. of the DIMACS Workshop, Immerman, N. and Kolaitis, P.H., Eds., Amsterdam: Elseiver, 1996, pp. 185\u2013214."},{"key":"6040_CR24","volume-title":"Model Checking","author":"E.M. Clarke","year":"2000","unstructured":"Clarke, E.M., Grumberg, O., and Peled, D., Model Checking, Cambridge: MIT, 2000. Translated under the title Verifikatsiya modelei programm: Model Checking, Moscow: MTSNMO, 2002."},{"key":"6040_CR25","first-page":"493","volume-title":"Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, Chapter 10","author":"K.R. Apt","year":"1990","unstructured":"Apt, K.R., Logic Programming, in Handbook of Theoretical Computer Science, Vol. B: Formal Models and Semantics, Chapter 10, Leeuwen, J., Ed., Amsterdam: Elsevier, 1990, pp. 493\u2013574."},{"key":"6040_CR26","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/0304-3975(82)90125-6","volume":"27","author":"D. Kozen","year":"1983","unstructured":"Kozen, D., Results on the Propositional \u03bc-Calculus, Theor. Comput. Sci., 1983, vol. 27, pp. 333\u2013354.","journal-title":"Theor. Comput. Sci."},{"key":"6040_CR27","volume-title":"The Temporal Logic of Reactive and Concurrent Systems: Specification","author":"Z. Manna","year":"1991","unstructured":"Manna, Z. and Pnueli, A., The Temporal Logic of Reactive and Concurrent Systems: Specification, Berlin: Springer, 1991."},{"key":"6040_CR28","unstructured":"Yi, K., Shilov, N.V., and Bodin E.V., Program Logics Made Simple, in Sistemnaya informatika (System Informatics), Novosibirsk, 2002, issue 8, pp. 206\u2013249."},{"key":"6040_CR29","volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M. and Johnson, D.S., Computers and Intractability\u2014A Guide to the Theory of NP-Completeness, New York: Freeman, 1979."},{"key":"6040_CR30","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H., Computational Complexity, Reading: Addison-Wesley, 1994."},{"key":"6040_CR31","series-title":"Lecture Notes in Computer Science","volume-title":"Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday","author":"M.I. Dekhtyar","year":"2008","unstructured":"Dekhtyar, M.I., Dikovsky, A.Ja., and Valiev, M.K., Temporal Verification of Probabilistic Multi-Agent Systems, in Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, Avron, A., Dershowitz, N., and Rabinovich, A., Eds., Lecture Notes in Computer Science, Berlin: Springer, 2008, vol. 4800."},{"key":"6040_CR32","first-page":"908","volume-title":"Trudy X natsional\u2019noi konferentsii po iskusstvennomu intellektu s mezdunarodnym uchastiem","author":"M.Yu. Burmistrov","year":"2006","unstructured":"Burmistrov, M.Yu., Valiev, M.K., Dekhtyar, M.I., and Dikovsky, A.Ya., On the Verification of Dynamical Properties of Systems of Interacting Agents, Trudy X natsional\u2019noi konferentsii po iskusstvennomu intellektu s mezdunarodnym uchastiem (Proc. of the X National Conf. on Artificial Intelligence with International Participation), Obninsk: Fizmatlit, 2006, pp. 908\u2013915."},{"key":"6040_CR33","volume-title":"Lecture Notes in AI","author":"A.S. Rao","year":"1996","unstructured":"Rao, A.S., AgentSpeak (L): BDI Agents Speak out in a Logical Computable Language, in Lecture Notes in AI, Berlin: Springer, 1996, vol. 1038."},{"key":"6040_CR34","first-page":"114","volume-title":"Sistemnaya informatika","author":"N.O. Garanina","year":"2006","unstructured":"Garanina, N.O. and Shilov, N.V., Verification of Combinatorial Logics of Knowledge, Actions, and Time in Models, in Sistemnaya informatika (System Informatics), Novosibirsk: Sib. Otd. RAN, 2006, issue 10, pp. 114\u2013173."},{"issue":"1\u20133","key":"6040_CR35","first-page":"347","volume":"72","author":"N.V. Shilov","year":"2006","unstructured":"Shilov, N.V., Garanina, N.O., and Choe, K.-M., Update and Abstraction in Model Checking of Knowledge and Branching Time, Fund. Inform., 2006, vol. 72, no. 1\u20133, pp. 347\u2013361.","journal-title":"Fund. Inform."},{"key":"6040_CR36","unstructured":"Emerson, E.A. and Lei, C.L., Efficient Model Checking in Fragments of the \u03bc-Calculus, Proc. of the IEEE Symposium on Logic in Computer Science, 1986."}],"container-title":["Programming and Computer Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S036176880905003X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S036176880905003X","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1134\/S036176880905003X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S036176880905003X.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:06:31Z","timestamp":1775009191000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S036176880905003X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,9]]},"references-count":36,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2009,9]]}},"alternative-id":["6040"],"URL":"https:\/\/doi.org\/10.1134\/s036176880905003x","relation":{},"ISSN":["0361-7688","1608-3261"],"issn-type":[{"value":"0361-7688","type":"print"},{"value":"1608-3261","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,9]]},"assertion":[{"value":"17 October 2008","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2009","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}