<?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-2018-5-506-524</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-746</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>Conference Papers</subject></subj-group></article-categories><title-group><article-title>О выразительных возможностях некоторых расширений линейной темпоральной логики</article-title><trans-title-group xml:lang="en"><trans-title>On the Expressive Power of Some Extensions of Linear Temporal Logic</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-0003-1499-2090</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>Gnatenko</surname><given-names>Anton</given-names></name></name-alternatives><bio xml:lang="ru"><p>студент.</p><p>Москва.</p></bio><bio xml:lang="en"><p>student.</p><p>Moscow.</p></bio><email xlink:type="simple">gnatenko.cmc@gmail.com</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-0002-3794-9565</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>Zakharov</surname><given-names>Vladimir</given-names></name></name-alternatives><bio xml:lang="ru"><p>доктор физ.-мат. наук, профессор.</p><p>Москва.</p></bio><bio xml:lang="en"><p>professor.</p><p>Moscow.</p></bio><email xlink:type="simple">zakh@cs.msu.ru</email><xref ref-type="aff" rid="aff-2"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Московский государственный университет им. М.В. Ломоносова.</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Lomonosov Moscow State University.</institution><country>Russian Federation</country></aff></aff-alternatives><aff-alternatives id="aff-2"><aff xml:lang="ru"><institution>Национальный исследовательский университет «Высшая школа экономики».</institution><country>Россия</country></aff><aff xml:lang="en"><institution>National Research University Higher School of Economics (HSE).</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2018</year></pub-date><pub-date pub-type="epub"><day>28</day><month>10</month><year>2018</year></pub-date><volume>25</volume><issue>5</issue><fpage>506</fpage><lpage>524</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Гнатенко А.Р., Захаров В.А., 2018</copyright-statement><copyright-year>2018</copyright-year><copyright-holder xml:lang="ru">Гнатенко А.Р., Захаров В.А.</copyright-holder><copyright-holder xml:lang="en">Gnatenko A., Zakharov V.</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/746">https://www.mais-journal.ru/jour/article/view/746</self-uri><abstract><p>Конечные автоматы, задающие преобразования потоков входных сигналов в последовательности элементарных действий, являются простейшей моделью вычислений, пригодной для описания поведения реагирующих систем. Это поведение проявляется в соответствии между потоком входных сигналов и последовательностью элементарных действий, выполняемых системой. Мы полагаем, что для формального описания поведения реагирующих систем такого рода требуются более сложные и выразительные средства спецификации, нежели традиционная темпоральная логика линейного времени LT L. В этой работе рассматривается новый язык формальных спецификаций LP-LT L, представляющий собой расширение темпоральной логики LT L, специально разработанное для описания свойств вычислений автоматов-преобразователей. Темпоральные операторы в формулах LP-LT L снабжены параметрами, в качестве которых используются множества слов (языки), описывающие потоки сигналов управления, поступающих на вход реагирующей системы. Базовые предикаты в формулах LP-LT L также определяются языками в алфавите элементарных действий; эти языки описывают ожидаемую реакцию системы в ответ на воздействия окружающей среды. В более ранних работах авторов этой статьи изучалась задача верификации конечных автоматов-преобразователей относительно спецификаций, представленных формулами логик LP-LT L и LP-CT L. Было показано, что для обеих логик эта задача алгоритмически разрешима. Цель данной работы — оценить выразительные возможности логики LP-LT L и сравнить ее с широко известными логиками, применяющимися в информатике для спецификации реагирующих систем. В логике LP-LT L были выделены два фрагмента LP-1-LT L и LP-n-LT L. Нам удалось установить, что язык спецификаций LP-1-LT L более выразителен, чем LT L, в то время как фрагмент LP-n-LT L обладает точно такими же выразительными возможностями, что и монадическая логика второго порядка S1S.</p></abstract><trans-abstract xml:lang="en"><p>One of the most simple models of computation which is suitable for representation of reactive systems behaviour is a finite state transducer which operates over an input alphabet of control signals and an output alphabet of basic actions. The behaviour of such a reactive system displays itself in the correspondence between flows of control signals and compositions of basic actions performed by the system. We believe that the behaviour of this kind requires more suitable and expressive means for formal specifications than the conventional LT L. In this paper, we define some new (as far as we know) extension LP-LT L of Linear Temporal Logic specifically intended for describing the properties of transducers computations. In this extension the temporal operators are parameterized by sets of words (languages) which represent distinguished flows of control signals that impact on a reactive system. Basic predicates in our variant of the temporal logic are also languages in the alphabet of basic actions of a transducer; they represent the expected response of the transducer to the specified environmental influences. In our earlier papers, we considered a model checking problem for LP-LT L and LP-CT L and showed that this problem has effective solutions. The aim of this paper is to estimate the expressive power of LP-LT L by comparing it with some well known logics widely used in the computer science for specification of reactive systems behaviour. We discovered that a restricted variant LP-1-LT L of our logic is more expressive than LTL and another restricted variant LP-n-LT L has the same expressive power as monadic second order logic S1S.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>темпоральные логики</kwd><kwd>выразительность</kwd><kwd>спецификация</kwd><kwd>верификация</kwd><kwd>автоматы Бюхи</kwd><kwd>бесконечные слова</kwd></kwd-group><kwd-group xml:lang="en"><kwd>temporal logics</kwd><kwd>expressive power</kwd><kwd>specification</kwd><kwd>verification</kwd><kwd>Buchi automata</kwd><kwd>infinite words</kwd></kwd-group><funding-group><funding-statement xml:lang="ru">РФФИ N 18-01-00854</funding-statement><funding-statement xml:lang="en">Russian Foundation for Basic Research, Grant N 18-01-00854</funding-statement></funding-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">Baier C., Katoen J., Principles of Model Checking, MIT Press, 2008.</mixed-citation><mixed-citation xml:lang="en">Baier C., Katoen J., Principles of Model Checking, MIT Press, 2008.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Clarke E. M., Gramberg O., Peled D. A., Model Checking, MIT Press, 1999.</mixed-citation><mixed-citation xml:lang="en">Clarke E. M., Gramberg O., Peled D. A., Model Checking, MIT Press, 1999.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Etessami K., Wilke T., "An Until Hierarchy and Other Applications of an EhrenfeuchtFraisse Game for Temporal Logic", Information and Computation, 160:1 (2000), 88-108.</mixed-citation><mixed-citation xml:lang="en">Etessami K., Wilke T., "An Until Hierarchy and Other Applications of an EhrenfeuchtFraisse Game for Temporal Logic", Information and Computation, 160:1 (2000), 88-108.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Fisher J. M., Ladner R. E., "Propositional dynamic logic of regular programs", Journal of Computer and System Sciences, 18 (1979), 194-211.</mixed-citation><mixed-citation xml:lang="en">Fisher J. M., Ladner R. E., "Propositional dynamic logic of regular programs", Journal of Computer and System Sciences, 18 (1979), 194-211.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Gabbay D., Pnueli A., Shelach S., Stavi J., "The temporal analysis of fairness", Proceedings of 7-th ACM Symposium on Principles of Programming Languages, 1980, 163-173.</mixed-citation><mixed-citation xml:lang="en">Gabbay D., Pnueli A., Shelach S., Stavi J., "The temporal analysis of fairness", Proceedings of 7-th ACM Symposium on Principles of Programming Languages, 1980, 163-173.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">Гнатенко А. Р., Захаров В. А., “О сложности верификации конечных автоматовпреобразователей над коммутативными полугруппами”, Труды 18-й Международной конференции "Проблемы теоретической кибернетики", 2017, 68–70.</mixed-citation><mixed-citation xml:lang="en">Gnatenko A. R., Zakharov V. A., \O slozhnosti verifikatsii avtomatov-preobrazovateley nad kommutativnymi polugruppami", Trudy 18 Mezhdunarodnoj konferentsii "Problemy teoteticheskoy kibernetiki", 2017, 68-70, (in Russian).</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Гнатенко А. Р., Захаров В. А., “О верификации конечных автоматов-преобразователей над полугруппами”, Труды Института системного программирования РАН, 30:3 (2018), 303–324.</mixed-citation><mixed-citation xml:lang="en">Gnatenko A. R., Zakharov V. A., \On the model checking of finite state transducers over semigroups", Proceedings of ISP RAS, 30:3, 303-324.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Harel D., Kozen D., Parikh P., "Process logic: Expressiveness, decidability, completeness", Journal of Computer and System Science, 25:2 (1982), 144-170.</mixed-citation><mixed-citation xml:lang="en">Harel D., Kozen D., Parikh P., "Process logic: Expressiveness, decidability, completeness", Journal of Computer and System Science, 25:2 (1982), 144-170.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">Henriksen J. J., Thiagarajan P. S., "Dynamic linear time temporal logic", Annals of Pure and Applied Logic, 96:1-3 (1999), 187-207.</mixed-citation><mixed-citation xml:lang="en">Henriksen J. J., Thiagarajan P. S., "Dynamic linear time temporal logic", Annals of Pure and Applied Logic, 96:1-3 (1999), 187-207.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Kamp J. A. W., Tense Logic and the Theory of Linear Order, PhD thesis, University of California, Los Angeles, 1968.</mixed-citation><mixed-citation xml:lang="en">Kamp J. A. W., Tense Logic and the Theory of Linear Order, PhD thesis, University of California, Los Angeles, 1968.</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Kozlova D. G., Zakharov V. A., "On the model checking of sequential reactive systems", Proceedings of the 25th International Workshop on Concurrency, Specification and Programming (CS&amp;P 2016), CEUR Workshop Proceedings, 1698, 2016, 233-244.</mixed-citation><mixed-citation xml:lang="en">Kozlova D. G., Zakharov V. A., "On the model checking of sequential reactive systems", Proceedings of the 25th International Workshop on Concurrency, Specification and Programming (CS&amp;P 2016), CEUR Workshop Proceedings, 1698, 2016, 233-244.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Kupferman O., Piterman N., Vardi M. Y., "Extended Temporal Logic Revisited", Proceedings of 12-th International Conference on Concurrency Theory, 2001, 519-535.</mixed-citation><mixed-citation xml:lang="en">Kupferman O., Piterman N., Vardi M. Y., "Extended Temporal Logic Revisited", Proceedings of 12-th International Conference on Concurrency Theory, 2001, 519-535.</mixed-citation></citation-alternatives></ref><ref id="cit13"><label>13</label><citation-alternatives><mixed-citation xml:lang="ru">Leucker M., Sanchez C., "Regular Linear Temporal Logic", Proceedings of the 4-th International Colloquium on Theoretical Aspects of Computing, 2007, 291-305.</mixed-citation><mixed-citation xml:lang="en">Leucker M., Sanchez C., "Regular Linear Temporal Logic", Proceedings of the 4-th International Colloquium on Theoretical Aspects of Computing, 2007, 291-305.</mixed-citation></citation-alternatives></ref><ref id="cit14"><label>14</label><citation-alternatives><mixed-citation xml:lang="ru">Manna Z., Wolper P., "Synthesis of Communicating Processes from Temporal Logic Specifications", Lecture Notes in Computer Science, 131, 1981, 253-281.</mixed-citation><mixed-citation xml:lang="en">Manna Z., Wolper P., "Synthesis of Communicating Processes from Temporal Logic Specifications", Lecture Notes in Computer Science, 131, 1981, 253-281.</mixed-citation></citation-alternatives></ref><ref id="cit15"><label>15</label><citation-alternatives><mixed-citation xml:lang="ru">Thomas W., "Automata on infinite objects", Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, 1990, 133-192.</mixed-citation><mixed-citation xml:lang="en">Thomas W., "Automata on infinite objects", Handbook of Theoretical Computer Science, volume B: Formal Models and Semantics, 1990, 133-192.</mixed-citation></citation-alternatives></ref><ref id="cit16"><label>16</label><citation-alternatives><mixed-citation xml:lang="ru">Vardi M. Y., Wolper P., "Yet Another Process Logic", Lecture Notes in Computer Science, 14, 1983, 501-512.</mixed-citation><mixed-citation xml:lang="en">Vardi M. Y., Wolper P., "Yet Another Process Logic", Lecture Notes in Computer Science, 14, 1983, 501-512.</mixed-citation></citation-alternatives></ref><ref id="cit17"><label>17</label><citation-alternatives><mixed-citation xml:lang="ru">Vardi M. Y., Wolper P., "An Automata-Theoretic Approach to Automatic Program Verification", Proceedings of the First Symposium on Logic in Computer Science, 1986, 322-331.</mixed-citation><mixed-citation xml:lang="en">Vardi M. Y., Wolper P., "An Automata-Theoretic Approach to Automatic Program Verification", Proceedings of the First Symposium on Logic in Computer Science, 1986, 322-331.</mixed-citation></citation-alternatives></ref><ref id="cit18"><label>18</label><citation-alternatives><mixed-citation xml:lang="ru">Vardi M. Y., "A Temporal Fixpoint Calculus", Proceedings of the 15-th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, 1989, 250-259.</mixed-citation><mixed-citation xml:lang="en">Vardi M. Y., "A Temporal Fixpoint Calculus", Proceedings of the 15-th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages, 1989, 250-259.</mixed-citation></citation-alternatives></ref><ref id="cit19"><label>19</label><citation-alternatives><mixed-citation xml:lang="ru">Wolper P., "Temporal Logic Can Be More Expressive", Information and Control, 56:1-2 (1983), 72-99.</mixed-citation><mixed-citation xml:lang="en">Wolper P., "Temporal Logic Can Be More Expressive", Information and Control, 56:1-2 (1983), 72-99.</mixed-citation></citation-alternatives></ref><ref id="cit20"><label>20</label><citation-alternatives><mixed-citation xml:lang="ru">Wolper P., Boigelot B., "Verifying systems with infinite but regular state spaces", Lecture Notes in Computer Science, 1427, 1998, 88-97.</mixed-citation><mixed-citation xml:lang="en">Wolper P., Boigelot B., "Verifying systems with infinite but regular state spaces", Lecture Notes in Computer Science, 1427, 1998, 88-97.</mixed-citation></citation-alternatives></ref><ref id="cit21"><label>21</label><citation-alternatives><mixed-citation xml:lang="ru">Zakharov V. A., "Equivalence checking problem for finite state transducers over semigroups", Lecture Notes in Computer Science, 9270, 2015, 208-221.524 Моделирование и анализ информационных систем. Т. 25, № 5 (2018) Modeling and Analysis of Information Systems. Vol. 25, No 5 (2018).</mixed-citation><mixed-citation xml:lang="en">Zakharov V. A., "Equivalence checking problem for finite state transducers over semigroups", Lecture Notes in Computer Science, 9270, 2015, 208-221.</mixed-citation></citation-alternatives></ref><ref id="cit22"><label>22</label><citation-alternatives><mixed-citation xml:lang="ru">Захаров В. А., Темербекова Г. Г., “О минимизации конечных автоматовпреобразователей над полугруппами”, Моделирование и анализ информационных систем, 23:6 (2016), 741–753.</mixed-citation><mixed-citation xml:lang="en">Zakharov V. A., Temerbekova G. G., "On the minimization of finite state trans-ducers over semigroups", Automatic Control and Computer Sciences, 51:7 (2017), 523-530.</mixed-citation></citation-alternatives></ref><ref id="cit23"><label>23</label><citation-alternatives><mixed-citation xml:lang="ru">Захаров В. А., Жайлауова Ш. Р., “О задаче минимизации последовательных программ”, Моделирование и анализ информационных систем, 24:4 (2017), 415–430.</mixed-citation><mixed-citation xml:lang="en">Zakharov V. A., Jaylauova S. R., "On the minimization problem for sequential programs", Automatic Control and Computer Sciences, 51:7 (2017), 689-700.</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>
