Adaptive Homing and Distinguishing Experiments for Nondeterministic Finite State Machines

1. Bochmann, G.V., Petrenko, A.: Protocol testing: review of methods and relevance for software testing. In: Proc. of International Symposium on Software Testing and Analysis, Seattle, pp. 109–123 (1994)

   Google Scholar 

2. Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A.R., Yevtushenko, N.: FSM-based conformance testing methods: a survey annotated with experimental evaluation. Information and Software Technology 52, 1286–1297 (2010)

   Article  Google Scholar 

3. Gill, A.: State-identification experiments in finite automata. Information and Control, 132–154 (1961)

   Google Scholar 

4. Kohavi, Z.: Switching and Finite Automata Theory. McGraw-Hill, New York (1978)

   MATH  Google Scholar 

5. Lee, D., Yannakakis, M.: Testing finite-state machines: state identification and verification. IEEE Trans. on Computers 43(3), 306–320 (1994)

   Article  MathSciNet  Google Scholar 

6. Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE 84(8), 1090–1123 (1996)

   Article  Google Scholar 

7. Simao, A., Petrenko, A., Maldonado, J.C.: Comparing finite state machine test. IET Software 3(2), 91–105 (2009)

   Article  Google Scholar 

8. Moore, E.F.: Gedanken-experiments on sequential machines. In: Automata Studies (Annals of Mathematical Studies no.1), pp. 129–153. Princeton University Press (1956)

   Google Scholar 

9. Hennie, F.C.: Fault detecting experiments for sequential circuits. In: Proc. of 5th Annual Symposium on Switching Circuit Theory and Logical Design, pp. 95–110. Princeton (1964)

   Google Scholar 

10. Petrenko, A., Simao, A., Yevtushenko, N.: Generating Checking Sequences for Nondeterministic Finite State Machines. In: Proc. of ICST 2012, pp. 310–319 (2012)

    Google Scholar 

11. Mathur, A.: Foundations of Software Testing. Addison Wesley (2008)

    Google Scholar 

12. Agibalov, G., Oranov, A.: Lectures on Automata Theory. Tomsk State University Publishers (1984) (in Russian)

    Google Scholar 

13. Ginsburg, S.: On the length of the smallest uniform experiment which distinguishes the terminal states of a machine. Journal of the ACM 5(3), 266–280 (1958)

    Article  MathSciNet  MATH  Google Scholar 

14. Hibbard, T.N.: Lest upper bounds on minimal terminal state experiments of two classes of sequential machines. Journal of the ACM 8(4), 601–612 (1961)

    Article  MATH  Google Scholar 

15. Sandberg, S.: Homing and Synchronization Sequences. In: Broy, M., Jonsson, B., Katoen, J.-P., Leucker, M., Pretschner, A. (eds.) Model-Based Testing of Reactive Systems. LNCS, vol. 3472, pp. 5–33. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

16. Ravikumar, B.: Parallel algorithms for finite automata problems. In: Rolim, J.D.P. (ed.) IPPS-WS 1998 and SPDP-WS 1998. LNCS, vol. 1388, p. 373. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

17. Spitsyna, N., El-Fakih, K., Yevtushenko, N.: Studying the separability relation between finite state machines. Software Testing, Verification and Reliability 17(4), 227–241 (2007)

    Article  Google Scholar 

18. Kushik, N., El-Fakih, K., Yevtushenko, N.: Preset and Adaptive Homing Experiments for Nondeterministic Finite State Machines. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol. 6807, pp. 215–224. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

19. Starke, P.: Abstract Automata. American Elsevier (1972)

    Google Scholar 

20. Kushik, N., Yevtushenko, N.: On the Length of Homing Sequences for Nondeterministic Finite State Machines. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 220–231. Springer, Heidelberg (2013)

    Google Scholar 

21. Zhang, F., Cheung, T.: Optimal Transfer Trees and Distinguishing Trees for Testing Observable Nondeterministic Finite-State Machines. IEEE Transactions on Software Engineering 19(1), 1–14 (2003)

    Article  Google Scholar 

22. Alur, R., Courcoubetis, C., Yannakakis, M.: Distinguishing tests for nondeterministic and probabilistic machines. In: Proc. of the 27th ACM Symposium on Theory of Computing, pp. 363–372 (1995)

    Google Scholar 

23. Petrenko, A., Yevtushenko, N.: Conformance Tests as Checking Experiments for Partial Nondeterministic FSM. In: Grieskamp, W., Weise, C. (eds.) FATES 2005. LNCS, vol. 3997, pp. 118–133. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

24. Gromov, M.L., Evtushenko, N.V., Kolomeets, A.V.: On the Synthesis of Adaptive Tests for Nondeterministic Finite State Machines. Progr. and Comp. Software 34(6), 322–329 (2008)

    Article  MATH  Google Scholar 

25. Petrenko, A., Yevtushenko, N.: Adaptive Testing of Deterministic Implementations Specified by Nondeterministic FSMs. In: Wolff, B., Zaïdi, F. (eds.) ICTSS 2011. LNCS, vol. 7019, pp. 162–178. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

26. Tretmans, J.: Model-Based Testing with Labelled Transition Systems: There is nothing More Practical than a Good Theory. Slides from the lecture at TAROT Summer School (2010), http://tarot2010.ist.tugraz.at/

27. Gromov, M., El-Fakih, K., Shabaldina, N., Yevtushenko, N.: Distinguing non-deterministic timed finite state machines. In: Lee, D., Lopes, A., Poetzsch-Heffter, A. (eds.) FMOODS/FORTE 2009. LNCS, vol. 5522, pp. 137–151. Springer, Heidelberg (2009)

    Google Scholar 

28. El-Fakih, K., Gromov, M., Shabaldina, N., Yevtushenko, N.: Distinguishing experiments for timed nondeterministic finite state machines. Acta Cybernetica (to appear)

    Google Scholar 

29. Petrenko, A., Yevtushenko, N., Bochmann, G.V.: Testing Deterministic Implementations from their Nondeterministic Specifications. In: Proc. of the IFIP Ninth International Workshop on Testing of Communicating Systems, pp. 125–140 (1996)

    Google Scholar 

Download references