Experiments on parallel composition of timed finite state machines
Автор: Sotnikov A.P., Shabaldina N.V., Gromov M.L.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 3 т.29, 2017 года.
Бесплатный доступ
In this paper, we continue our work that is devoted to the parallel composition of Timed Finite State Machines (TFSMs). We consider the composition of TFSMs with timeouts and output delays. We held experiments in order to estimate how often parallel composition of nondeterministic TFSMs (with and without timeouts) has infinite sets of output delays. To conduct these experiments we have created two tools: the first one for converting TFSMs into automata (this tool is integrated into BALM-II), the second one for converting the global automaton of the composition into TFSM. As it was suggested in earlier works, we describe the infinite sets of output delays by linear functions, and it is important to know how often these sets of linear functions appear to justify the importance of future investigations of the TFSM parallel compositions (especially for deriving cascade composition). Results of the experiments show significant amount (around 50 %) of TFSMs with infinite number of output delays. We also estimate the size of the global automaton and the composed TFSM. In the experiments, we do not consider global automata with the huge number of states (more then 10000).
Timed finite state machine, parallel composition, balm-ii
Короткий адрес: https://sciup.org/14916437
IDR: 14916437 | DOI: 10.15514/ISPRAS-2017-29(3)-13
Список литературы Experiments on parallel composition of timed finite state machines
- Gill A. Introduction to the theory of finite state machines, New-York, McGraw-Hill, 1962.
- 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.
- 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 (date of access: 21.04.2016).
- Gregorio Diaz, Juan-Jos e Pardo, Mar a-Emilia Cambronero, Valent n Valero, and Fernando Cuartero. Automatic Translation of WS-CDL Choreographies to Timed 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. 17 DOI: 10.1007/11549970
- 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. Bibliography 102 SITIS '07. Third International IEEE Conference on, pages 417-426, Dec 2007 DOI: 10.1109/SITIS.2007.110
- R. Alur and D. L. Dill. A theory of timed automata. Theoretical computer science. 1994. Vol.126, Iss. 2. pp. 183-235.
- Springintveld J., Vaandrager F. and D’Argenio P. Testing timed automata. Theoretical Computer Science, 254 (1-2). pp. 225-257, 2001.
- 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.
- 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.
- 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.
- Tvardovskii A., Yevtushenko N. Minimizing timed Finite State Machines. Vestnik TGU , 2014. Vol. 4 (29). pp. 77-82.
- O. Kondratyeva, N. Yevtushenko, and A. Cavalli. Parallel composition of nondeterministic finite state machines with timeouts. Journal of Control and Computer Science. Tomsk State University, Russia. 2014. Vol. 2(27). pp. 73-81.
- O. Kondratyeva, N. Yevtushenko, A. Cavalli. Solving parallel equations for Finite State Machines with Timeouts. Trudy ISP RАN/Proc. ISP RAS, vol. 26, issue 6, pp. 85-98 DOI: 10.15514/ISPRAS-2014-26(6)-8
- Shabaldina N., Gromov M. Using BALM-II for deriving parallel composition of timed finite state machines with outputs delays and timeouts: work-in-progress. System Informatics , № 8, 2016, pp. 33-42.
- Gromov M.L, Shabaldina N.V. Using balm-ii for deriving cascade parallel composition of timed finite state machines. Modeling and Analysis of Information Systems , 23:3 (2016). pp. 699-712.
- http://www.uppaal.com/(date of access: 21.04.2016)
- 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.
