Evaluating the complexity of deriving adaptive $$S'$$-homing and $$S'$$-synchronizing sequences for nondeterministic FSMs

Alur, R., Courcoubetis, C., & Yannakakis, M. (1995). Distinguishing tests for nondeterministic and probabilistic machines. In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 29 May-1 June 1995, Las Vegas, Nevada, USA, pp. 363–372. https://doi.org/10.1145/225058.225161

Chow, T. S. (1978). Testing software design modeled by finite-state machines. IEEE Transactions on Software Engineering, 4(3), 178–187.

Gill, A. (1962). Introduction to the Theory of Finite-state Machines. New York: McGraw-Hill.

Hennie, F. C. (1964). Fault detecting experiments for sequential circuits. In 5th Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, USA, November 11-13, 1964, pp. 95–110. https://doi.org/10.1109/SWCT.1964.8

Hierons, R. M., & Ural, H. (2002). Reduced length checking sequences. IEEE Trans. Computers, 51(9), 1111–1117. https://doi.org/10.1109/TC.2002.1032630

Ito, M. & Shikishima-Tsuji, K. (2004). Some results on directable automata. In Theory Is Forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday, pp. 125–133. https://doi.org/10.1007/978-3-540-27812-2n12

Kushik, N., El-Fakih, K., & Yevtushenko, N. (2013). Adaptive homing and distinguishing experiments for nondeterministic finite state machines. In Testing Software and Systems - 25th IFIP WG 6.1 International Conference, ICTSS 2013, Istanbul, Turkey, November 13-15, 2013, Proceedings, pp. 33–48. https://doi.org/10.1007/978-3-642-41707-8n3

Kushik, N., El-Fakih, K., Yevtushenko, N., & Cavalli, A. R. (2016a). On adaptive experiments for nondeterministic finite state machines. STTT, 18(3), 251–264. https://doi.org/10.1007/s10009-014-0357-7

Kushik, N., López, J., Cavalli, A. R., & Yevtushenko, N. (2016b). Improving protocol passive testing through gedanken experiments with finite state machines. In 2016 IEEE International Conference on Software Quality, Reliability and Security, QRS 2016, Vienna, Austria, August 1-3, 2016, pp. 315–322. https://doi.org/10.1109/QRS.2016.43

Kushik, N., & Yevtushenko, N. (2013). On the length of homing sequences for nondeterministic finite state machines. In Implementation and Application of Automata - 18th International Conference, CIAA 2013, Halifax, NS, Canada, July 16-19, 2013. Proceedings, pp. 220–231.

Kushik, N., & Yevtushenko, N. (2015). Adaptive homing is in P. In Proceedings Tenth Workshop on Model Based Testing, MBT 2015, London, UK, 18th April 2015., pp. 73–78.

Kushik, N., Yevtushenko, N., & Yenigün, H. (2016c). Reducing the complexity of checking the existence and derivation of adaptive synchronizing experiments for nondeterministic fsms. In Proceedings of the International Workshop on Domain Specific Model-based App Roaches to Verification and Validation, AMARETTO@MODELSWARD 2016, Rome, Italy, February 19-21, 2016., pp. 83–90. https://doi.org/10.5220/0005854500830090

Lee, D., & Yannakakis, M. (1994). Testing finite-state machines: State identification and verification. IEEE Transaction on Computers,43(3), 306–320. https://doi.org/10.1109/12.272431

Lee, D., & Yannakakis, M. (1996). Principles and methods of testing finite state machines-a survey. Proceedings of the IEEE,84, 1090–1123. https://doi.org/10.1109/5.533956

Petrenko, A., & Yevtushenko, H. (2005). Conformance tests as checking experiments for partial nondeterministic FSM. In Formal Approaches to Software Testing, 5th International Workshop, FATES 2005, Edinburgh, UK, July 11, 2005, Revised Selected Papers, pp. 118–133. https://doi.org/10.1007/11759744n9

Sandberg, S. (2004). Homing and synchronizing sequences. In Model-Based Testing of Reactive Systems, Advanced Lectures [The volume is the outcome of a research seminar that was held in Schloss Dagstuhl in January 2004], pp. 5–33. https://doi.org/101007/11498490n2

Türker, U. C., & Yenigün, H. (2014). Hardness and inapproximability of minimizing adaptive distinguishing sequences. Formal Methods in System Design,44(3), 264–294.

von Bochmann, G., & Petrenko, A. (1994). Protocol testing: Review of methods and relevance for software testing. In Proceedings of the 1994 International Symposium on Software Testing and Analysis, ISSTA 1994, Seattle, WA, USA, August 17-19, 1994, pp. 109–124. https://doi.org/10.1145/186258.187153

Yenigün, H., Yevtushenko, N., & Kushik, N. (2017). The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic fsms. Inf. Process. Lett., 127, 49–53. https://doi.org/10.1016/j.ipl.2017.07.001

Yevtushenko, N., Kuliamin, V. V., & Kushik, N. (2019). Evaluating the complexity of deriving adaptive homing, synchronizing and distinguishing sequences for nondeterministic fsms. In Testing Software and Systems - 31st IFIP WG 6.1 International Conference, ICTSS 2019, Paris, France, October 15-17, 2019, Proceedings, pp. 86–103. https://doi.org/10.1007/978-3-030-31280-0n6