<?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-715-728</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-409</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>Построение каскадной параллельной композиции временных автоматов с использованием BALM-II</article-title><trans-title-group xml:lang="en"><trans-title>Using balm-ii for Deriving Cascade Parallel Composition of Timed Finite State Machines</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-0002-2990-8245</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>Gromov</surname><given-names>M. L.</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. физ.-мат. наук, пр. Ленина, 36, г. Томск, 634050 Россия</p></bio><bio xml:lang="en"><p>PhD, 36 Lenin av., Tomsk 634050, Russia</p></bio><email xlink:type="simple">maxim.leo.gromov@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-1958-550X</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>Shabaldina</surname><given-names>N. V.</given-names></name></name-alternatives><bio xml:lang="ru"><p>канд. техн. наук, доцент, пр. Ленина, 36, г. Томск, 634050 Россия</p></bio><bio xml:lang="en"><p>PhD, 36 Lenin av., Tomsk 634050, Russia</p></bio><email xlink:type="simple">nataliamailbox@mail.ru</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>Tomsk State University</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>715</fpage><lpage>728</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">Gromov M.L., Shabaldina N.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/409">https://www.mais-journal.ru/jour/article/view/409</self-uri><abstract><p>В данной работе мы рассмотрели задачу построения каскадной параллельной композиции временных автоматов. Построение такой композиции можно свести к поэтапному построению бинарной параллельной композиции. Известно, что если каждая из компонент бинарной параллельной композиции есть временной автомат с константными задержками выходов, то результатом композиции может быть временной автомат, множество задержек выходных символов которого бесконечно и задано при помощи конечного множества линейных функций. Поэтому задача построения каскадной композиции временных автоматов с константными задержками выходов сводится к построению ряда бинарных параллельных композиций временных автоматов, задержки выходов которых заданы либо в виде констант, либо в виде множества линейных функций. В данной работе мы уточняем определение временного автомата, обращая особое внимание на описание задержки выходного символа. В качестве инструмента для построения композиции мы используем balm-ii, и поэтому рассматриваем переход от временного автомата с задержками выходов в виде множества линейных функций к соответствующему полуавтомату. Мы предлагаем свою процедуру построения полуавтомата, которая, в отличие от известной процедуры, не требует последующей детерминизации полученного полуавтомата. Кроме того, мы пошагово описываем, каким образом построить композицию соответствующих полуавтоматов при помощи balm-ii, а также обсуждаем процедуру обратного преобразования от полуавтомата композиции к временному автомату, отмечая некоторые нюансы, связанные с композицией временных автоматов с задержками выходов в виде множества линейных функций. В работе приведён пример, иллюстрирующий построение каскадной параллельной композиции временных автоматов.</p></abstract><trans-abstract xml:lang="en"><p>In this paper, we consider the problem of deriving a cascade parallel composition of timed ﬁnite state machines (TFSMs). In order to build such a composition we can derive the corresponding binary parallel compositions step-by-step. It is known that if each component of a binary parallel composition is TFSM with output delays that are natural numbers or zero, the result of the composition can be TFSM with output delays that are sets of linear functions. So, the problem of deriving a cascade composition of TFSMs with constant output delays is reduced to the problem of deriving several binary parallel compositions of TFSMs with output delays that are sets of constants or linear functions. In this work, we reﬁne the deﬁnition of TFSM and pay special attention to the description of an output delay function. As a tool for deriving the composition we consider balm-ii, and in consequence we study the ways of constructing the corresponding automaton for TFSM with output delays as a set of linear functions. We suggest a new procedure for constructing such an automaton, and unlike the known procedure our procedure does not require further determinization of the derived automaton. Moreover, we describe step by step how to build the composition of the derived automaton by using balm-ii, and discuss a procedure of reverse transformation from the global automaton to TFSM in case when the components are TFSMs with output delays that are sets of linear functions. We use an application example in order to illustrate derivation of the cascade parallel composition of TFSMs.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>временные автоматы</kwd><kwd>каскадная параллельная композиция</kwd><kwd>balm-ii</kwd></kwd-group><kwd-group xml:lang="en"><kwd>timed ﬁnite state machines</kwd><kwd>cascade parallel composition</kwd><kwd>balm-ii</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">Moore E. F., “Gedanken-experiments on Sequential Machines”, Automata Studies, Annals of Mathematical Studies, 34 (1956), 129–153.</mixed-citation><mixed-citation xml:lang="en">Moore E. F., “Gedanken-experiments on Sequential Machines”, Automata Studies, Annals of Mathematical Studies, 34 (1956), 129–153.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">Gill A., Introduction to the theory of ﬁnite-state machines, McGraw-Hill, New-York, 1962, 207 pp.</mixed-citation><mixed-citation xml:lang="en">Gill A., Introduction to the theory of ﬁnite-state machines, McGraw-Hill, New-York, 1962, 207 pp.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">Yevtushenko N., Villa T., Brayton R., Petrenko A. and Sangiovanni-Vincentelli A., “Solution of parallel language equations for logic synthesis”, The Proceedings of the International Conference on Computer-Aided Design, 2001, 103–110.</mixed-citation><mixed-citation xml:lang="en">Yevtushenko N., Villa T., Brayton R., Petrenko A. and Sangiovanni-Vincentelli A., “Solution of parallel language equations for logic synthesis”, The Proceedings of the International Conference on Computer-Aided Design, 2001, 103–110.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">Castagnetti G., Piccolo M., Villa T., Yevtushenko N., Mishchenko A. and Brayton R. K., Solving Parallel Equations with balm-ii, Technical Report No UCB/EECS-2012-181, Electrical Engineering and Computer Sciences University of California at Berkeley, 2012, http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-181.pdf.</mixed-citation><mixed-citation xml:lang="en">Castagnetti G., Piccolo M., Villa T., Yevtushenko N., Mishchenko A. and Brayton R. K., Solving Parallel Equations with balm-ii, Technical Report No UCB/EECS-2012-181, Electrical Engineering and Computer Sciences University of California at Berkeley, 2012, http://www.eecs.berkeley.edu/Pubs/TechRpts/2012/EECS-2012-181.pdf.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">Alur R. and Dill D. L., “A theory of timed automata”, Theoretical computer science, 126:2 (1994), 183–235.</mixed-citation><mixed-citation xml:lang="en">Alur R. and Dill D. L., “A theory of timed automata”, Theoretical computer science, 126:2 (1994), 183–235.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">El-Fakih K., Gromov M, Shabaldina N. and Yevtushenko N., “Distinguishing Experiments for Timed Non-Deterministic Finite State Machines”, Acta Cybernetica, 21:2 (2013), 205– 222.</mixed-citation><mixed-citation xml:lang="en">El-Fakih K., Gromov M, Shabaldina N. and Yevtushenko N., “Distinguishing Experiments for Timed Non-Deterministic Finite State Machines”, Acta Cybernetica, 21:2 (2013), 205– 222.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">Kondratyeva O., Yevtushenko N. and Cavalli A., “Parallel composition of nondeterministic ﬁnite state machines with timeouts”, Journal of Control and Computer Science of Tomsk State University, 2:27 (2014), 73–81.</mixed-citation><mixed-citation xml:lang="en">Kondratyeva O., Yevtushenko N. and Cavalli A., “Parallel composition of nondeterministic ﬁnite state machines with timeouts”, Journal of Control and Computer Science of Tomsk State University, 2:27 (2014), 73–81.</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">Kondratyeva O., Yevtushenko N. and Cavalli A., “Solving parallel equations for Finite State Machines with Timeouts”, The Proceedings of ISP RAS, 26:6 (2014), 85–98.</mixed-citation><mixed-citation xml:lang="en">Kondratyeva O., Yevtushenko N. and Cavalli A., “Solving parallel equations for Finite State Machines with Timeouts”, The Proceedings of ISP RAS, 26:6 (2014), 85–98.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">http://www.uppaal.com/.</mixed-citation><mixed-citation xml:lang="en">http://www.uppaal.com/.</mixed-citation></citation-alternatives></ref><ref id="cit10"><label>10</label><citation-alternatives><mixed-citation xml:lang="ru">Zhigulin M., Yevtushenko N., Maag S. and Cavalli A. R., “FSM-based test derivation strategies for systems with timeouts.”, Proceedings of the international conference QSIC, 2011, 141–149..</mixed-citation><mixed-citation xml:lang="en">Zhigulin M., Yevtushenko N., Maag S. and Cavalli A. R., “FSM-based test derivation strategies for systems with timeouts.”, Proceedings of the international conference QSIC, 2011, 141–149..</mixed-citation></citation-alternatives></ref><ref id="cit11"><label>11</label><citation-alternatives><mixed-citation xml:lang="ru">Gromov M. and Shabaldina N., “Using balm-iifor deriving parallel composition of timed ﬁnite state machines with outputs delays and timeouts: work-in-progress”, System Informatics, 8 (2016), 33–42.</mixed-citation><mixed-citation xml:lang="en">Gromov M. and Shabaldina N., “Using balm-iifor deriving parallel composition of timed ﬁnite state machines with outputs delays and timeouts: work-in-progress”, System Informatics, 8 (2016), 33–42.</mixed-citation></citation-alternatives></ref><ref id="cit12"><label>12</label><citation-alternatives><mixed-citation xml:lang="ru">Springintveld J., Vaandrager F. and D’Argenio P. R., “Testing timed automata”, Theoretical Computer Science, 254:1–2 (March 2001), 225–257.</mixed-citation><mixed-citation xml:lang="en">Springintveld J., Vaandrager F. and D’Argenio P. R., “Testing timed automata”, Theoretical Computer Science, 254:1–2 (March 2001), 225–257.</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>
