Эксперименты по построению параллельной композиции временных автоматов
https://doi.org/10.15514/ISPRAS-2017-29(3)-13
Аннотация
В данной работе мы продолжаем наши исследования параллельной композиции временных конечных автоматов. Мы рассматриваем композицию временных автоматов с таймаутами и задержками выходных символов. Для того чтобы оценить, насколько часто в параллельной композиции недетерминированных временных автоматов (с таймаутами и без таймаутов) возникают бесконечные множества задержек выходных символов, мы провели компьютерные эксперименты. Для проведения таких экспериментов мы реализовали два инструмента: первый позволяет преобразовать временной конечный автомат в полуавтомат (данный инструмент встроен в BALM-II), второй позволяет преобразовать глобальный полуавтомат композиции во временной автомат. Ориентируясь на известные работы по данной тематике, мы описываем бесконечные множества задержек выходных символов конечным образом, а именно, при помощи линейных функций, и нужно знать, как часто такое множество линейных функций возникает, чтобы оценить важность дальнейших исследований параллельной композиции временных автоматов (особенно случая каскадной композиции). Результаты экспериментов показали, что в значительном количестве случаев (около 50 %) временной автомат композиции содержит бесконечное множество задержек выходных символов. Кроме того, мы оценили размер глобального полуавтомата и автомата композиции. При проведении экспериментов мы не рассматривали глобальные полуавтоматы с большим числом состояний (более 10000).
Об авторах
А. П. Сотников
Томский государственный университет
Россия
Россия
Н. В. Шабалдина
Томский государственный университет
Россия
Россия
М. Л. Громов
Томский государственный университет
Россия
Россия
Список литературы
1. Gill A. Introduction to the theory of finite state machines, New-York, McGraw-Hill, 1962.
2. N. Yevtushenko, T. Villa, R. Brayton, A. Petrenko, and A. Sangiovanni-Vincentelli. Solution of parallel language equations for logic synthesis. In The Proceedings of the International Conference on Computer-Aided Design. 2001. pp. 103–110.
3. G. Castagnetti, M. Piccolo, T. Villa, N. Yevtushenko, A. Mishchenko, Robert K. Brayton. 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 (дата доступа 21.04.2016).
4. Gregorio Diaz, Juan-Jos e Pardo, Mar a-Emilia Cambronero, Valent n Valero, and Fernando Cuartero. Automatic Translation of WS-CDL Choreographies to Timed
5. Automata, volume 3670 of Lecture Notes in Computer Science, book section 17, pages 230{242. Springer Berlin Heidelberg, 2005. ISBN 978-3-540-28701-8. doi:
6. 1007/11549970 17
7. M. Lallali, F. Zaidi, and A. Cavalli. Timed modeling of web services composition for automatic testing. In Signal-Image. Technologies and Internet-Based System, 2007.
8. Bibliography 102 SITIS '07. Third International IEEE Conference on, pages 417- 426, Dec 2007. DOI: 10.1109/SITIS.2007.110.
9. R. Alur and D. L. Dill. A theory of timed automata. Theoretical computer science. 1994. Vol.126, Iss. 2. pp. 183–235.
10. Springintveld J., Vaandrager F. and D’Argenio P. Testing timed automata. Theoretical Computer Science, 254 (1-2). pp. 225-257, 2001.
11. Kushik N., Lopez J., Cavalli A., Yevtushenko N. Improving Protocol Passive Testing through 'Gedanken' Experiments with Finite State Machines. Proceedings 2016 IEEE International Conference on Software Quality, Reliability and Security, pp. 315-322.
12. Hierons R., Turker U. Parallel Algorithms for Testing Finite State Machines: Generating UIO Sequences. IEEE Transactions on Software Engineering, 42(11),7429774. pp. 1077-1091, 2016.
13. K. El-Fakih, M. Gromov, N. Shabaldina, N. Yevtushenko. Distinguishing Experiments for Timed Non-Deterministic Finite State Machines. Acta Cybernetica. 2013. Vol. 21, № 2. pp. 205–222.
14. А.С. Твардовский, Н.В. Евтушенко. К минимизации автоматов с временными ограничениями. Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика, 2014. № 4 (29), стр. 77-82
15. О.В. Кондратьева, Н.В. Евтушенко, А.Р. Кавалли. Параллельная композиция конечных автоматов с таймаутами. Вестн. Том. гос. ун-та. Управление, вычислительная техника и информатика, 2014. № 2 (27), стр. 73–81
16. О.В. Кондратьева, Н.В. Евтушенко, А.Р. Кавалли. Решение автоматных уравнений для временных автоматов относительно параллельной композиции. Труды ИСП РАН, том 26, вып. 6, стр. 85–98
17. Shabaldina N., Gromov M. Using BALM-II for deriving parallel composition of timed finite state machines with outputs delays and timeouts: work-in-progress. Системная информатика, № 8, 2016, pp. 33-42.
18. Громов М. Л., Шабалдина Н. В. Построение каскадной параллельной композиции временных автоматов в balm-ii. Моделирование и анализ информационных систем, Т. 23, No 6 (2016), стр. 699-712.
19. http://www.uppaal.com/ (дата доступа 21.04.2016)
20. N. Shabaldina, M. Gromov. FSMTest-1.0: a manual for researches. Proceedings of IEEE East-West Design & Test Symposium (EWDTS’2015). Ukraine, Kharkov: SCITEPRESS, 2015, pp. 216-219.
Рецензия
Для цитирования:
Сотников А.П., Шабалдина Н.В., Громов М.Л. Эксперименты по построению параллельной композиции временных автоматов. Труды Института системного программирования РАН. 2017;29(3):233-246. https://doi.org/10.15514/ISPRAS-2017-29(3)-13
For citation:
Sotnikov A.P., Shabaldina N.V., Gromov M.L. Experiments on Parallel Composition of Timed Finite State Machines. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(3):233-246. https://doi.org/10.15514/ISPRAS-2017-29(3)-13
Послать статью по эл. почте 