Checking experiments with non-observable tree FSMs
https://doi.org/10.15514/ISPRAS-2015-27(6)-28
Abstract
The paper addresses the problem of deriving preset checking experiments for non-observable FSMs. The fault model is considered to be a ‘white box’ where all possible implementations are explicitly enumerated. We show that if the specification FMS has a tree structure then it is possible to derive a complete checking experiment that has polynomial length.
References
1. M.P. Vasilevskij. O raspoznavanii neispravnosti avtomatov [Failure diagnosis of automata]. Kibernetika [Cybernetics], № 4, 1973, pp. 98-108 (in Russian).
2. F. Hennie. Fault-Detecting Experiments for Sequential Circuits. Proc. Fifth Ann. Symp. Switching Circuit Theory and Logical Design, 1964. P. 95-110.
3. E. Moore. Gedanken-experiments on sequential machines Automata Studies, Annals of Mathematical Studies, No.1, 1956. P. 129-153.
4. D. Lee M. Yannakakis. Testing Finite-State Machines: State Identification and Verification. IEEE Transactions on Computers, 1994, Volume 43, Issue 3. P. 306-320.
5. S. Sandberg. Homing and Synchronization Sequences. Lecture Notes in Computer Science, № 3472, 2005. P. 5-33.
6. N.V. Evtushenko, A.F. Petrenko, M.V. Vetrova. Nedeterminirovannye avtomaty: analiz i sintez Ch. 1: Otnoshenija i operacii : ucheb. posobie [Nondeterministic FSMs : analysis and synthesis, Chapter 1 : relations and operations : course support book]. Tomsk : Tom. gos. un-t, 2006. 142 p. (in Russian)
7. N. Spitsyna, K. El-Fakih, N. Yevtushenko. Studying the separability relation between finite state machines. Softw. Test., Verif. Reliab., 2007, Volume 17, Issue 4. P. 227-241.
8. N. Kushik, N. Yevtushenko, A. Cavalli. On Testing against Partial Non-observable Specifications. Proceedings of the 9th International Conference on the Quality of Information and Communications Technology, 2014. P. 230-233.
Review
For citations:
Kushik N. Checking experiments with non-observable tree FSMs. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2015;27(6):441-450. (In Russ.) https://doi.org/10.15514/ISPRAS-2015-27(6)-28
Email this article 