{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T23:01:40Z","timestamp":1773615700517,"version":"3.50.1"},"reference-count":31,"publisher":"Allerton Press","issue":"7","license":[{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,12,1]],"date-time":"2021-12-01T00:00:00Z","timestamp":1638316800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Aut. Control Comp. Sci."],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.3103\/s0146411621070154","type":"journal-article","created":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T09:15:43Z","timestamp":1643706943000},"page":"738-750","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Deriving Homing Sequences for Finite State Machines with Timed Guards"],"prefix":"10.3103","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7705-7214","authenticated-orcid":false,"given":"A. S.","family":"Tvardovskii","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4006-1161","authenticated-orcid":false,"given":"N. V.","family":"Yevtushenko","sequence":"additional","affiliation":[]}],"member":"1627","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"key":"7401_CR1","volume-title":"Introduction to the Theory of Finite-State Machines","author":"A. Gill","year":"1962","unstructured":"Gill, A., Introduction to the Theory of Finite-State Machines, McGraw-Hill, 1962."},{"key":"7401_CR2","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/12.272431","volume":"43","author":"D. Lee","year":"1994","unstructured":"Lee, D. and Yannakakis, M., Testing finite state machines: State identification and verification, IEEE Trans. Comput., 1994, vol. 43, no. 3, pp. 306\u2013320.","journal-title":"IEEE Trans. Comput."},{"key":"7401_CR3","doi-asserted-by":"publisher","first-page":"601","DOI":"10.1145\/321088.321098","volume":"8","author":"T.N. Hibbard","year":"1961","unstructured":"Hibbard, T.N., Least upper bounds on minimal terminal state experiments for two classes of sequential machines, J. ACM, 1961, vol. 8, no. 4, pp. 601\u2013612.","journal-title":"J. ACM"},{"key":"7401_CR4","volume-title":"Switching and Finite Automata Theory","author":"Z. Kohavi","year":"1978","unstructured":"Kohavi, Z., Switching and Finite Automata Theory, McGraw-Hill, 1978."},{"key":"7401_CR5","unstructured":"Starke, P., Abstract Automata, Am. Elsevier, 1972."},{"key":"7401_CR6","doi-asserted-by":"crossref","unstructured":"Bochmann, G. and Petrenko, A., Protocol testing: Review of methods and relevance for software testing, Proc. of International Symposium on Software Testing and Analysis, 1994, pp. 109\u2013124.","DOI":"10.1145\/186258.187153"},{"key":"7401_CR7","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1016\/j.ipl.2015.01.002","volume":"115","author":"G.-V. Jourdan","year":"2015","unstructured":"Jourdan, G.-V., Ural, H., and Yenigun, H., Reduced checking sequences using unreliable reset, Inf. Process. Lett., 2015, vol. 115, no. 5, pp. 532\u2013535.","journal-title":"Inf. Process. Lett."},{"key":"7401_CR8","doi-asserted-by":"crossref","unstructured":"Kushik, N., L\u00f3pez, J., Cavalli, A., and Yevtushenko, N., Improving protocol passive testing through \u201cGedanken\u201d experiments with finite state machines, IEEE International Conference on Software Thality, Reliability and Security, 2016, pp. 315\u2013322.","DOI":"10.1109\/QRS.2016.43"},{"key":"7401_CR9","doi-asserted-by":"crossref","unstructured":"Hennie, F., Fault-detecting experiments for sequential circuits, Proceedings of Fifth Annual Symposium on Circuit Theory and Logical Design, 1965, pp. 95\u2013110.","DOI":"10.1109\/SWCT.1964.8"},{"key":"7401_CR10","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1109\/TSE.1978.231496","volume":"4","author":"T.S. Chow","year":"1978","unstructured":"Chow, T.S., Testing software design modeled by finite-state machines, IEEE Trans. Software Eng., 1978, vol. 4, no. 3, pp. 178\u2013187.","journal-title":"IEEE Trans. Software Eng."},{"key":"7401_CR11","series-title":"Homing sequence derivation with quantified Boolean satisfiability","volume-title":"Testing Software and Systems","author":"H.-E. Wang","year":"2017","unstructured":"Wang, H.-E., Tu, K.-H., Jiang, J.-H.R., and Kushik, N., Homing sequence derivation with quantified Boolean satisfiability, in Testing Software and Systems, Springer, 2017, pp. 230\u2013242."},{"key":"7401_CR12","doi-asserted-by":"crossref","unstructured":"Yenigun, H., Yevtushenko, N., Kushik, N., and L\u00f3pez, J., The effect of partiality and adaptivity on the complexity of FSM state identification problems, Proc. ISP RAS, 2018, vol. 30, no. 1, pp. 7\u201324.","DOI":"10.15514\/ISPRAS-2018-30(1)-1"},{"key":"7401_CR13","volume-title":"On the length of homing sequences for nondeterministic finite state machines, in Implementation and Application of Automata","author":"N. Kushik","year":"2013","unstructured":"Kushik, N. and Yevtushenko, N., On the length of homing sequences for nondeterministic finite state machines, in Implementation and Application of Automata, Springer, 2013, pp. 220\u2013231."},{"key":"7401_CR14","series-title":"Homing and synchronizing sequences","volume-title":"Model-Based Testing of Reactive Systems","author":"S. Sandberg","year":"2005","unstructured":"Sandberg, S., Homing and synchronizing sequences, in Model-Based Testing of Reactive Systems, Springer, 2005, pp. 5\u201333."},{"key":"7401_CR15","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/j.comnet.2004.09.009","volume":"48","author":"E. Bayse","year":"2005","unstructured":"Bayse, E., Cavalli, A.R., N\u00fa\u00f1ez, M., and Za\u00efdi, F., A passive testing approach based on invariants: Application to the WAP, Comput. Networks, 2005, vol. 48, no. 2, pp. 247\u2013266.","journal-title":"Comput. Networks"},{"key":"7401_CR16","series-title":"Preset and adaptive homing experiments for nondeterministic finite state machines","volume-title":"Implementation and Application of Automata","author":"N. Kushik","year":"2011","unstructured":"Kushik, N., El-Fakih, K., and Yevtushenko, N., Preset and adaptive homing experiments for nondeterministic finite state machines, in Implementation and Application of Automata, Springer, 2011, pp. 215\u2013224."},{"key":"7401_CR17","series-title":"Adaptive homing and distinguishing experiments for nondeterministic finite state machines","volume-title":"Testing Software and Systems","author":"N. Kushik","year":"2013","unstructured":"Kushik, N., El-Fakih, K., and Yevtushenko, N., Adaptive homing and distinguishing experiments for nondeterministic finite state machines, in Testing Software and Systems, Springer, 2013, pp. 33\u201348."},{"key":"7401_CR18","series-title":"Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines","volume-title":"Testing Software and Systems","author":"N. Kushik","year":"2015","unstructured":"Kushik, N. and Yenig\u00fcn, H., Heuristics for deriving adaptive homing and distinguishing sequences for nondeterministic finite state machines, in Testing Software and Systems, Springer, 2015, pp. 243\u2013248."},{"key":"7401_CR19","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ipl.2017.07.001","volume":"127","author":"H. Yenig\u00fcn","year":"2017","unstructured":"Yenig\u00fcn, H., Yevtushenko, N., and Kushik, N., The complexity of checking the existence and derivation of adaptive synchronizing experiments for deterministic FSMs, Inf. Process. Lett., 2017, vol. 127, pp. 49\u201353.","journal-title":"Inf. Process. Lett."},{"key":"7401_CR20","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/s10703-009-0065-1","volume":"34","author":"M. Krichen","year":"2009","unstructured":"Krichen, M. and Tripakis, S., Conformance testing for real-time systems, Formal Methods Syst. Des., 2009, vol.\u00a034, no. 3, pp. 238\u2013304.","journal-title":"Formal Methods Syst. Des."},{"key":"7401_CR21","doi-asserted-by":"crossref","unstructured":"El-Fakih, K., Yevtushenko, N., and Fouchal, H., Testing timed finite state machines with guaranteed fault coverage, Proc. of the 21st IFIP WG 6.1 Int. Conf. on Testing of Software and Communication Systems and 9th Int. FATES Workshop, 2009, pp. 66\u201380.","DOI":"10.1007\/978-3-642-05031-2_5"},{"key":"7401_CR22","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1016\/j.comnet.2007.10.002","volume":"52","author":"M. Merayo","year":"2008","unstructured":"Merayo, M., Nunez, M., and Rodriguez, I., Formal testing from timed finite state machines, Comput. Networks: Int. J. Comput. Telecommun. Networking, 2008, vol. 52, no. 2, pp. 432\u2013460.","journal-title":"Comput. Networks: Int. J. Comput. Telecommun. Networking"},{"key":"7401_CR23","doi-asserted-by":"crossref","unstructured":"Bresolin, D., El-Fakih, K., Villa, T., and Yevtushenko, N., Deterministic timed finite state machines: Equivalence checking and expressive power, International Conference GANDALF, 2014, pp. 203\u2013216.","DOI":"10.4204\/EPTCS.161.18"},{"key":"7401_CR24","series-title":"Distinguishing non-deterministic timed finite state machines","volume-title":"Formal Techniques for Distributed Systems","author":"M. Gromov","year":"2009","unstructured":"Gromov, M., El-Fakih, K., Shabaldina, N., and Yevtushenko, N., Distinguishing non-deterministic timed finite state machines, in Formal Techniques for Distributed Systems, Springer, 2009, pp. 137\u2013151."},{"key":"7401_CR25","doi-asserted-by":"publisher","first-page":"724","DOI":"10.3103\/S0146411617070318","volume":"51","author":"A.S. Tvardovskii","year":"2017","unstructured":"Tvardovskii, A.S., El-Fakih, K., Gromov, M., and Yevtushenko, N., Testing timed nondeterministic finite state machines with the guaranteed fault coverage, Autom. Control Comput. Sci., 2017, vol. 51, no. 7, pp. 724\u2013730.","journal-title":"Autom. Control Comput. Sci."},{"key":"7401_CR26","first-page":"1","volume":"17","author":"A. Tvardovskii","year":"2020","unstructured":"Tvardovskii, A. and Yevtushenko, N., Deriving homing sequences for Finite State Machines with timed guards, Syst. Inf., 2020, vol. 17, pp. 1\u201310.","journal-title":"Syst. Inf."},{"key":"7401_CR27","volume-title":"Algebraic Structure Theory of Sequential Machines","author":"J. Hartmanis","year":"1966","unstructured":"Hartmanis, J. and Stearns, R., Algebraic Structure Theory of Sequential Machines, Prentice-Hall, 1966."},{"key":"7401_CR28","doi-asserted-by":"crossref","unstructured":"Vinarskii, E., Tvardovskii, A., Evtushenko, L., and Yevtushenko, N., Deriving adaptive homing sequences for weakly initialized nondeterministic FSMs, 2019 IEEE East-West Design & Test Symposium (EWDTS), IEEE, 2019.","DOI":"10.1109\/EWDTS.2019.8884403"},{"key":"7401_CR29","series-title":"Evaluating the complexity of deriving adaptive homing, synchronizing and distinguishing sequences for nondeterministic FSMs","volume-title":"Testing Software and Systems","author":"N. Yevtushenko","year":"2019","unstructured":"Yevtushenko, N., Kuliamin, V., and Kushik, N., Evaluating the complexity of deriving adaptive homing, synchronizing and distinguishing sequences for nondeterministic FSMs, in Testing Software and Systems, Springer, 2019, pp. 86\u2013103."},{"key":"7401_CR30","doi-asserted-by":"crossref","unstructured":"Vinarskii, E. and Yevtushenko, N., Evaluating length of a shortest adaptive homing sequence for weakly initialized FSMs, 2020 IEEE East-West Design & Test Symposium (EWDTS), 2020.","DOI":"10.1109\/EWDTS50664.2020.9225043"},{"key":"7401_CR31","doi-asserted-by":"publisher","first-page":"73","DOI":"10.4204\/EPTCS.180.5","volume":"180","author":"N. Kushik","year":"2015","unstructured":"Kushik, N. and Yevtushenko, N., Adaptive homing is in P, Electron. Proc. Theor. Comput. Sci., 2015, vol. 180, pp. 73\u201378.","journal-title":"Electron. Proc. Theor. Comput. Sci."}],"container-title":["Automatic Control and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411621070154.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.3103\/S0146411621070154","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.3103\/S0146411621070154.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T22:03:29Z","timestamp":1773612209000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.3103\/S0146411621070154"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12]]},"references-count":31,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["7401"],"URL":"https:\/\/doi.org\/10.3103\/s0146411621070154","relation":{},"ISSN":["0146-4116","1558-108X"],"issn-type":[{"value":"0146-4116","type":"print"},{"value":"1558-108X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12]]},"assertion":[{"value":"9 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 November 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no conflicts of interest.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"CONFLICT OF INTEREST"}}]}}