<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">mais</journal-id><journal-title-group><journal-title xml:lang="ru">Моделирование и анализ информационных систем</journal-title><trans-title-group xml:lang="en"><trans-title>Modeling and Analysis of Information Systems</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1818-1015</issn><issn pub-type="epub">2313-5417</issn><publisher><publisher-name>Yaroslavl State University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.18255/1818-1015-2016-6-703-714</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-408</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Оригинальные статьи</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="en"><subject>Articles</subject></subj-group></article-categories><title-group><article-title>Подход к верификации семейства мультиагентных систем разрешения конфликтов</article-title><trans-title-group xml:lang="en"><trans-title>An Approach to Veriﬁcation of a Family of Multi- agent Systems for Conﬂict Resolution</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0001-9734-3808</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Гаранина</surname><given-names>Н. О.</given-names></name><name name-style="western" xml:lang="en"><surname>Garanina</surname><given-names>N. O.</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. физ.-мат. наук, проспект Лаврентьева, 6, г. Новосибирск, 630090 Россия</p></bio><bio xml:lang="en"><p>PhD, 6 Acad. Lavrentjev pr., Novosibirsk 630090, Russia</p></bio><email xlink:type="simple">garanina@iis.nsk.su</email><xref ref-type="aff" rid="aff-1"/></contrib><contrib contrib-type="author" corresp="yes"><contrib-id contrib-id-type="orcid">https://orcid.org/0000-0001-8731-3058</contrib-id><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Сидорова</surname><given-names>Е. А.</given-names></name><name name-style="western" xml:lang="en"><surname>Sidorova</surname><given-names>E. A.</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. физ.-мат. наук, проспект Лаврентьева, 6, г. Новосибирск, 630090 Россия</p></bio><bio xml:lang="en"><p>PhD, 6 Acad. Lavrentjev pr., Novosibirsk 630090, Russia</p></bio><email xlink:type="simple">lena@iis.nsk.su</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Институт систем информатики им. А.П. Ершова СО РАН</institution><country>Россия</country></aff><aff xml:lang="en"><institution>A.P. Ershov Institute of Informatics Systems, SB RAS</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2016</year></pub-date><pub-date pub-type="epub"><day>20</day><month>12</month><year>2016</year></pub-date><volume>23</volume><issue>6</issue><fpage>703</fpage><lpage>714</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Гаранина Н.О., Сидорова Е.А., 2016</copyright-statement><copyright-year>2016</copyright-year><copyright-holder xml:lang="ru">Гаранина Н.О., Сидорова Е.А.</copyright-holder><copyright-holder xml:lang="en">Garanina N.O., Sidorova E.A.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.mais-journal.ru/jour/article/view/408">https://www.mais-journal.ru/jour/article/view/408</self-uri><abstract><p>В данной работе мы описываем метод верификации для семейств распределенных систем, которые порождаются контекстно-зависимой сетевой грамматикой специального вида. Эта грамматика содержит специальные нетерминальные символы ䷘ квази-терминалы. Квази-терминалы однозначно соответствуют терминалам грамматики и могут задавать процессы,которые определяются слиянием базовых процессов системы, в то время как нетерминалы задают сети параллельных композиций этих процессов. Данный метод верификации основан на техниках верификации моделей и абстракции. Абстрактная репрезентативная модель семейства систем зависит от задающей их грамматики и верифицируемых свойств системы. Эта модель симулирует поведение заданных систем таким образом, что свойства, которые выполняются в репрезентативной модели, также выполняются и во всех заданных системах. Проверку свойств репрезентативной модели можно осуществлять с помощью метода проверки моделей. Свойства порождаемых систем специфицируются с помощью универсальной логики ветвящегося времени ∀CTL с конечными детерминированными автоматами в качестве атомарных формул. Мы показываем, что предложенный метод верификации можно применять для проверки некоторых свойств мультиагентных систем разрешения конфликтов, в частности, систем разрешения неоднозначностей при пополнении онтологий. Также показано, что этот подход можно использовать для верификации вычислений на подрешетках, являющихся подграфами решеток вычислений, например, для вычисления четности числа работающих процессов.</p></abstract><trans-abstract xml:lang="en"><p>In the paper, we describe a veriﬁcation method for families of distributed systems generated by context-sensitive network grammar of a special kind. This grammar includes special non-terminal symbols, so called quasi-terminals, which uniquely correspond to grammar terminals. These quasi-terminals specify processes which are merging of base system processes, in contrast to simple nonterminals which specify networks of parallel compositions of the processes. The method is based on model checking technique and abstraction. An abstract representative model for a family of systems depends on their speciﬁcation grammar and system properties to be veriﬁed. This model simulates the behaviour of the systems in such a way that the properties which hold for the representative model are satisﬁed for all these systems. The properties of the representative model can be veriﬁed by model checking method. The properties of a generated system are speciﬁed by universal branching time logic ∀CTL with ﬁnite deterministic automata as atomic formulas. We show the use of this method for veriﬁcation of some properties of a multiagent system for conﬂict resolution, in particular, for context-dependent disambiguation in ontology population. We also suggest that this approach should be used for veriﬁcation of computations on sub-grids which are sub-graphs of computation grids. In particular, we consider the computation of parity of the active processes number in a sub-grid.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>проверка моделей</kwd><kwd>контекстно-зависимая сетевая грамматика</kwd><kwd>мультиагентные системы</kwd><kwd>абстракция</kwd></kwd-group><kwd-group xml:lang="en"><kwd>model checking</kwd><kwd>context-sensitive network grammar</kwd><kwd>multi-agent systems</kwd><kwd>abstractions</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Bergenti F., Franchi E., Poggi A., “Selected models for agent-based simulation of social networks”, Proc. of 3rd Symposium on Social Networks and Multiagent Systems (SNAMAS 2011), 2011, 27–32.</mixed-citation><mixed-citation xml:lang="en">Bergenti F., Franchi E., Poggi A., “Selected models for agent-based simulation of social networks”, Proc. of 3rd Symposium on Social Networks and Multiagent Systems (SNAMAS 2011), 2011, 27–32.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Clarke E. M., Grumberg O., Jha S., “Verifying Parameterized Networks”, ACM Transactions on Programming Languages and Systems, 19:5 (1997), 726–750.</mixed-citation><mixed-citation xml:lang="en">Clarke E. M., Grumberg O., Jha S., “Verifying Parameterized Networks”, ACM Transactions on Programming Languages and Systems, 19:5 (1997), 726–750.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Clarke E. M., Grumberg O., Peled D., Model Checking, MIT Press, 1999.</mixed-citation><mixed-citation xml:lang="en">Clarke E. M., Grumberg O., Peled D., Model Checking, MIT Press, 1999.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Dassow J., “Grammars With Regulated Rewriting”, Formal Languages and Applications, Studies in Fuzziness and Soft Computing, 148, 2004, 249–273.</mixed-citation><mixed-citation xml:lang="en">Dassow J., “Grammars With Regulated Rewriting”, Formal Languages and Applications, Studies in Fuzziness and Soft Computing, 148, 2004, 249–273.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">De Gennaro M. C., Jadbabaie A., “Decentralized Control of Connectivity for Multi-Agent Systems”, Proc. of 45th IEEE Conference on Decision and Control, 2006, 3628–3633.</mixed-citation><mixed-citation xml:lang="en">De Gennaro M. C., Jadbabaie A., “Decentralized Control of Connectivity for Multi-Agent Systems”, Proc. of 45th IEEE Conference on Decision and Control, 2006, 3628–3633.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Fagin R., Halpern J. Y., Moses Y., Vardi M. Y., Reasoning about Knowledge, MIT Press, 1995.</mixed-citation><mixed-citation xml:lang="en">Fagin R., Halpern J. Y., Moses Y., Vardi M. Y., Reasoning about Knowledge, MIT Press, 1995.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Garanina N. O., Sidorova E .A., “Ontology Population as Algebraic Information System Processing Based on Multi-agent Natural Language Text Analysis Algorithms”, Programming and Computer Software, 41:3 (2015), 140–148.</mixed-citation><mixed-citation xml:lang="en">Garanina N. O., Sidorova E .A., “Ontology Population as Algebraic Information System Processing Based on Multi-agent Natural Language Text Analysis Algorithms”, Programming and Computer Software, 41:3 (2015), 140–148.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Garanina N., Sidorova E., “An Approach to Ambiguity Resolution for Ontology Population”, Proc. of 24th International Workshop on Concurrency, Speciﬁcation, and Programming, (CS&amp;P 2015) (Rzeszow, Poland, 2015, Sep. 28–30), 1, 2015, 27–32.</mixed-citation><mixed-citation xml:lang="en">Garanina N., Sidorova E., “An Approach to Ambiguity Resolution for Ontology Population”, Proc. of 24th International Workshop on Concurrency, Speciﬁcation, and Programming, (CS&amp;P 2015) (Rzeszow, Poland, 2015, Sep. 28–30), 1, 2015, 27–32.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Garanina N. O., Sidorova E. A., Anokhin S. A., “Conﬂict Resolution in Multi-agent Systems with Typed Connections for Ontology Population”, Perspectives of System Informatics, Lecture Notes in Computer Science, 9609, 2016, 116–129.</mixed-citation><mixed-citation xml:lang="en">Garanina N. O., Sidorova E. A., Anokhin S. A., “Conﬂict Resolution in Multi-agent Systems with Typed Connections for Ontology Population”, Perspectives of System Informatics, Lecture Notes in Computer Science, 9609, 2016, 116–129.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Hopcroft J. E., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.</mixed-citation><mixed-citation xml:lang="en">Hopcroft J. E., Ullman J. D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Huhns M. N., Stephens L. M., “Multiagent Systems and Societies of Agents”, Multiagent Systems: A Modern Approach to Distributed Artiﬁcial Intelligence, MIT Press, 1999, 79– 120.</mixed-citation><mixed-citation xml:lang="en">Huhns M. N., Stephens L. M., “Multiagent Systems and Societies of Agents”, Multiagent Systems: A Modern Approach to Distributed Artiﬁcial Intelligence, MIT Press, 1999, 79– 120.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Tel G., Introduction to Distributed Algorithms, Cambridge University Press, 2000.</mixed-citation><mixed-citation xml:lang="en">Tel G., Introduction to Distributed Algorithms, Cambridge University Press, 2000.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Wooldridge M., An Introduction to Multiagent Systems, Willey&amp;Sons Ltd, 2002.</mixed-citation><mixed-citation xml:lang="en">Wooldridge M., An Introduction to Multiagent Systems, Willey&amp;Sons Ltd, 2002.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
