{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T09:33:03Z","timestamp":1773653583624,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,11,21]],"date-time":"2014-11-21T00:00:00Z","timestamp":1416528000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Softw Tools Technol Transfer"],"published-print":{"date-parts":[[2016,6]]},"DOI":"10.1007\/s10009-014-0357-7","type":"journal-article","created":{"date-parts":[[2014,11,21]],"date-time":"2014-11-21T11:30:03Z","timestamp":1416569403000},"page":"251-264","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":25,"title":["On adaptive experiments for nondeterministic finite state machines"],"prefix":"10.1007","volume":"18","author":[{"given":"Natalia","family":"Kushik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khaled","family":"El-Fakih","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nina","family":"Yevtushenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ana R.","family":"Cavalli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,11,21]]},"reference":[{"key":"357_CR1","doi-asserted-by":"crossref","unstructured":"Bochmann, G.V., Petrenko, A.: Protocol testing: review of methods and relevance for software testing. In: Proceedings of International Symposium on Software Testing and Analysis, Seattle, pp. 109\u2013123 (1994)","DOI":"10.1145\/186258.187153"},{"key":"357_CR2","doi-asserted-by":"crossref","first-page":"1286","DOI":"10.1016\/j.infsof.2010.07.001","volume":"52","author":"R Dorofeeva","year":"2010","unstructured":"Dorofeeva, R., El-Fakih, K., Maag, S., Cavalli, A.R., Yevtushenko, N.: FSM-based conformance testing methods: a survey annotated with experimental evaluation. Inf. Softw. Technol. 52, 1286\u20131297 (2010). (Elsevier)","journal-title":"Inf. Softw. Technol."},{"key":"357_CR3","doi-asserted-by":"crossref","unstructured":"Gill, A.: State-identification experiments in finite automata. Inf. Control 4, 132\u2013154 (1961)","DOI":"10.1016\/S0019-9958(61)80003-X"},{"key":"357_CR4","volume-title":"Switching and Finite Automata Theory","author":"Z Kohavi","year":"1978","unstructured":"Kohavi, Z.: Switching and Finite Automata Theory. McGraw- Hill, New York (1978)"},{"key":"357_CR5","doi-asserted-by":"crossref","unstructured":"Lee, D., Yannakakis, M.: Testing finite-state machines: state identification and verification. IEEE Trans. Comput. 43(3), 306\u2013320 (1994)","DOI":"10.1109\/12.272431"},{"issue":"8","key":"357_CR6","doi-asserted-by":"crossref","first-page":"1090","DOI":"10.1109\/5.533956","volume":"84","author":"D Lee","year":"1996","unstructured":"Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines-a survey. Proc IEEE 84(8), 1090\u20131123 (1996)","journal-title":"Proc IEEE"},{"key":"357_CR7","doi-asserted-by":"crossref","unstructured":"Simao, A., Petrenko, A., Maldonado, J.C.: Comparing finite state machine test. IET Softw. 3(2), 91\u2013105 (2009)","DOI":"10.1049\/iet-sen.2008.0018"},{"key":"357_CR8","doi-asserted-by":"crossref","unstructured":"Moore, E.F.: Gedanken-experiments on sequential machines. In: Automata Studies: Annals of Mathematics Studies, vol. 34, pp. 129\u2013153. Princeton Univ. Press, Princeton (1956)","DOI":"10.1515\/9781400882618-006"},{"key":"357_CR9","doi-asserted-by":"crossref","unstructured":"Hennie, F.C.: Fault detecting experiments for sequential circuits. In: Proceedings of 5th Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, pp. 95\u2013110 (1964)","DOI":"10.1109\/SWCT.1964.8"},{"key":"357_CR10","doi-asserted-by":"crossref","unstructured":"Petrenko, A., Simao, A., Yevtushenko, N.: Generating checking sequences for nondeterministic finite state machines. In: Proceedings of IEEE International Conference on Software Testing, Verification, and Validation (ICST-2012), pp. 310\u2013319 (2012)","DOI":"10.1109\/ICST.2012.111"},{"key":"357_CR11","unstructured":"Mathur, A.: Foundations of Software Testing. Addison Wesley, Boston (2008)"},{"key":"357_CR12","volume-title":"Lectures on Automata Theory","author":"G Agibalov","year":"1984","unstructured":"Agibalov, G., Oranov, A.: Lectures on Automata Theory. Tomsk State University Publishers, Tomsk (1984). (in Russian)"},{"key":"357_CR13","doi-asserted-by":"crossref","unstructured":"Ginsburg, S.: On the length of the smallest uniform experiment which distinguishes the terminal states of a machine. J. ACM 5(3), 266\u2013280 (1958)","DOI":"10.1145\/320932.320938"},{"key":"357_CR14","doi-asserted-by":"crossref","unstructured":"Hibbard, T.N.: Lest upper bounds on minimal terminal state experiments of two classes of sequential machines. J. ACM 8(4), 601\u2013612 (1961)","DOI":"10.1145\/321088.321098"},{"key":"357_CR15","first-page":"5","volume":"3472","author":"S Sandberg","year":"2005","unstructured":"Sandberg, S.: Homing and synchronization sequences, model based testing of reactive systems. LNCS 3472, 5\u201333 (2005)","journal-title":"LNCS"},{"key":"357_CR16","first-page":"373","volume":"1388","author":"B Ravikumar","year":"1998","unstructured":"Ravikumar, B.: Parallel algorithms for finite automata problems. LNCS 1388, 373 (1998)","journal-title":"LNCS"},{"key":"357_CR17","doi-asserted-by":"crossref","unstructured":"Milner, R.: A Calculus of Communicating Systems. Springer, Berlin (1980)","DOI":"10.1007\/3-540-10235-3"},{"key":"357_CR18","doi-asserted-by":"crossref","unstructured":"Alur, R. Courcoubetis, C., Yannakakis, M.: Distinguishing tests for nondeterministic and probabilistic machines. In: Proceedings of the 27th ACM Symposium on Theory of Computing, pp. 363\u2013372 (1995)","DOI":"10.1145\/225058.225161"},{"key":"357_CR19","doi-asserted-by":"crossref","unstructured":"Spitsyna, N., El-Fakih, K., Yevtushenko, N.: Studying the separability relation between finite state machines. Softw. Test. Verif. Reliab. 17(4), 227\u2013241 (2007)","DOI":"10.1002\/stvr.374"},{"key":"357_CR20","doi-asserted-by":"crossref","unstructured":"Hierons, R.M., Jourdan, G.-V., Ural, H., Yenigun, H.: Checking sequence construction using adaptive and preset distinguishing sequences. In: Proceedings of the Software Engineering and Formal Methods, 2009 Seventh IEEE International Conference on Software Engineering and Formal Methods, pp. 157\u2013166 (2009)","DOI":"10.1109\/SEFM.2009.12"},{"key":"357_CR21","doi-asserted-by":"crossref","unstructured":"Kushik, N., El-Fakih, K., Yevtushenko, N.: Preset and adaptive homing experiments for nondeterministic finite state machines. In: Proceedings of the 16th International Conference on Implementation and Application of Automata (CIAA 2011), Blois, France, LNCS 6807, pp 215\u2013224 (2011)","DOI":"10.1007\/978-3-642-22256-6_20"},{"key":"357_CR22","doi-asserted-by":"crossref","unstructured":"Kushik, N.: Methods for deriving homing and distinguishing experiments for nondeterministic FSMs. Ph.D. thesis, Tomsk State University, p. 137 (2013)","DOI":"10.1007\/978-3-642-41707-8_3"},{"issue":"7","key":"357_CR23","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/j.ipl.2011.12.012","volume":"112","author":"I Hwang","year":"2012","unstructured":"Hwang, I., Yevtushenko, N., Cavalli, A.: Tight bound on the length of distinguishing sequences for non-observable nondeterministic finite-state machines with a polynomial number of inputs and outputs. Inf. Process. Lett. 112(7), 298\u2013301 (2012)","journal-title":"Inf. Process. Lett."},{"key":"357_CR24","doi-asserted-by":"crossref","unstructured":"Kushik, N., Yevtushenko, N.: On the length of homing sequences for nondeterministic finite state machines. In: Proceedings of the 18th International Conference on Implementation and Application of Automata (CIAA 2013), pp. 220\u2013231 (2013)","DOI":"10.1007\/978-3-642-39274-0_20"},{"key":"357_CR25","volume-title":"Abstract Automata","author":"P Starke","year":"1972","unstructured":"Starke, P.: Abstract Automata. American Elsevier, New York (1972)"},{"key":"357_CR26","doi-asserted-by":"crossref","unstructured":"Zhang, F., Cheung, T.: Optimal transfer trees and distinguishing trees for testing observable nondeterministic finite-state machines. IEEE Trans. Softw. Eng. 19(1), 1\u201314 (2003)","DOI":"10.1109\/TSE.2003.1166585"},{"key":"357_CR27","doi-asserted-by":"crossref","unstructured":"Petrenko, A., Yevtushenko, N.: Conformance tests as checking experiments for partial nondeterministic FSM. In: Proceedings of FATES\u20192005, pp. 118\u2013133 (2005)","DOI":"10.1007\/11759744_9"},{"key":"357_CR28","doi-asserted-by":"crossref","unstructured":"Gromov, M.L., Evtushenko, N.V., Kolomeets, A.V.: On the synthesis of adaptive tests for nondeterministic finite state machines. Progr. Comput. Softw. 34(6), 322\u2013329 (2008)","DOI":"10.1134\/S0361768808060030"},{"key":"357_CR29","doi-asserted-by":"crossref","unstructured":"Petrenko, A., Yevtushenko, N.: Adaptive testing of deterministic implementations specified by nondeterministic FSMs. In: Proceedings of the International Conference on Testing Software and Systems (ICTSS 2011), LNCS 7019, pp. 162\u2013178 (2011)","DOI":"10.1007\/978-3-642-24580-0_12"},{"key":"357_CR30","unstructured":"Tretmans, J.: Model-based testing with labelled transition systems: there is nothing more practical than a good theory. Slides from the lecture in TAROT Summer School\u20192010 (2010). http:\/\/tarot2010.ist.tugraz.at\/slides\/Tretmans.pdf"},{"key":"357_CR31","doi-asserted-by":"crossref","unstructured":"Gromov, M., El-Fakih, K., Shabaldina, N., Yevtushenko, N.: Distinguishing non-deterministic timed finite state machines. In: Proceedings of the FMOODS\/FORTE\u20192009, pp. 137\u2013151 (2009)","DOI":"10.1007\/978-3-642-02138-1_9"},{"key":"357_CR32","doi-asserted-by":"crossref","unstructured":"El-Fakih, K., Gromov, M., Shabaldina, N., Yevtushenko, N.: Distinguishing experiments for timed nondeterministic finite state machines. Acta. Cybern. 21(2), 205\u2013222 (2013)","DOI":"10.14232\/actacyb.21.2.2013.1"},{"key":"357_CR33","unstructured":"Andres, C., Yevtushenko, N., Cavalli A.R.: Modeling and testing the European train control system. Technical Report TechRca 14\u201303-2013, Telecom Sudparis (2013)"},{"key":"357_CR34","doi-asserted-by":"crossref","unstructured":"Leeke, M., A.: Evaluating the use of reference run models in fault injection analysis. In: Proceedings of the 15th IEEE Pacific Rim International Symposium on Dependable Computing (PRDC\u20192009), pp. 121\u2013124 (2009)","DOI":"10.1109\/PRDC.2009.28"},{"key":"357_CR35","doi-asserted-by":"crossref","unstructured":"Petrenko, A., Yevtushenko, N., Bochmann, G.V.: Testing Deterministic Implementations from their Nondeterministic Specifications. In: Proceedings of the IFIP Ninth International Workshop on Testing of Communicating Systems, pp. 125\u2013140 (1996)","DOI":"10.1007\/978-0-387-35062-2_10"},{"key":"357_CR36","doi-asserted-by":"crossref","unstructured":"Kushik, N., El-Fakih, K., Yevtushenko, N.: Adaptive homing and distinguishing experiments for nondeterministic finite state machines. In: Proceedings of the 25th International Conference on Testing Software and Systems (ICTSS 2013), Istanbul, Turkey, LNCS 8254, pp. 33\u201348 (2013)","DOI":"10.1007\/978-3-642-41707-8_3"}],"container-title":["International Journal on Software Tools for Technology Transfer"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-014-0357-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10009-014-0357-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10009-014-0357-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T14:06:03Z","timestamp":1566050763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10009-014-0357-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,21]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,6]]}},"alternative-id":["357"],"URL":"https:\/\/doi.org\/10.1007\/s10009-014-0357-7","relation":{},"ISSN":["1433-2779","1433-2787"],"issn-type":[{"value":"1433-2779","type":"print"},{"value":"1433-2787","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,21]]}}}