{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,26]],"date-time":"2026-09-26T02:54:06Z","timestamp":1790391246143,"version":"4.1.0"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"9","license":[{"start":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T00:00:00Z","timestamp":1655251200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"Ministry of Science and Higher Education of Russian Federation","award":["075-15-2020-788"],"award-info":[{"award-number":["075-15-2020-788"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,9,18]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>State identification is the well-known problem in the automata theory that is aimed to determining the current or initial state of a system under test and this fact is widely used in the model-based testing of software and hardware systems. When modern systems are modeled, it is necessary to take into account the timed aspects and for this reason classical Finite State Machines (FSM) are extended by clock variables. In this work, we study the homing problem for FSMs with timeouts (TFSM). For this purpose, we introduce the notion of a timed homing sequence (HS) that is different from that for classical FSMs and propose a method for checking the existence and deriving a timed HS if it exists. A proposed method is based on the FSM abstraction of a TFSM, i.e. on a classical FSM that partially describes the behavior of a corresponding TFSM and inherits many of its properties. Since timeouts allow the system to move from state to state without input impact, we define a timed HS as a sequence that sets a TFSM to a stable state where the system can stay infinitely long waiting for an input.<\/jats:p>","DOI":"10.1093\/comjnl\/bxac069","type":"journal-article","created":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T21:40:57Z","timestamp":1655242857000},"page":"2181-2190","source":"Crossref","is-referenced-by-count":1,"title":["Deriving homing sequences for Finite State Machines with timeouts"],"prefix":"10.1093","volume":"66","author":[{"given":"Aleksandr","family":"Tvardovskii","sequence":"first","affiliation":[{"name":"Department of Applied Mathematics and Computer Science , National Research Tomsk State University, Tomsk 634050, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nina","family":"Yevtushenko","sequence":"additional","affiliation":[{"name":"Department of Software Engineering , Ivannikov Institute for System Programming of the RAS, Moscow 109004, Russia"},{"name":"Department of Computer Science , National Research University Higher School of Economics, Moscow 101000, Russia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2022,6,15]]},"reference":[{"key":"2023091720460550600_ref1","volume-title":"Introduction to the Theory of Finite-State Machines","author":"Gill","year":"1962"},{"key":"2023091720460550600_ref2","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1109\/12.272431","article-title":"Testing finite state machines: state identification and verification","volume":"43","author":"Lee","year":"1994","journal-title":"IEEE Trans. Comput."},{"key":"2023091720460550600_ref3","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/321088.321098","article-title":"Least upper bounds on minimal terminal state experiments of two classes of sequential machines","volume":"8","author":"Hibbard","year":"1961","journal-title":"J. ACM"},{"key":"2023091720460550600_ref4","volume-title":"Switching and Finite Automata Theory","author":"Kohavi","year":"1978"},{"key":"2023091720460550600_ref5","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1145\/186258.187153","volume-title":"Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis (ISSTA\u201994), Seattle, 17\u201319 August","author":"Bochmann","year":"1994"},{"key":"2023091720460550600_ref6","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1016\/j.ipl.2015.01.002","article-title":"Reduced checking sequences using unreliable reset","volume":"115","author":"Jourdan","year":"2015","journal-title":"Inf. Process. Lett."},{"key":"2023091720460550600_ref7","first-page":"315","volume-title":"Proceedings of IEEE International Conference on Software Quality, Reliability and Security, Vienna, Austria, 1\u20133 August","author":"Kushik","year":"2016"},{"key":"2023091720460550600_ref8","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TSE.1978.231496","article-title":"Test design modeled by finite-state machines","volume":"4","author":"Chow","year":"1978","journal-title":"IEEE Trans. Softw. Eng."},{"key":"2023091720460550600_ref9","first-page":"95","volume-title":"Proceedings of Fifth Annual Symposium on Circuit Theory and Logical Design, Princeton, USA, 11\u201313 November","author":"Hennie","year":"1965"},{"key":"2023091720460550600_ref10","first-page":"230","volume-title":"Proceedings of International Conference on Testing Software and Systems (ICTSS), St. Petersburg, Russia, 9\u201311 October","author":"Wang","year":"2017"},{"key":"2023091720460550600_ref11","doi-asserted-by":"crossref","first-page":"7","DOI":"10.15514\/ISPRAS-2018-30(1)-1","article-title":"The effect of partiality and adaptivity on the complexity of FSM state identification problems","volume":"30","author":"Yenigun","year":"2018","journal-title":"Trudy ISP RAN\/Proc. ISP RAS"},{"key":"2023091720460550600_ref12","first-page":"220","volume-title":"Proceedings of the 18th International Conference on Implementation and Application of Automata, Halifax, Canada, 16\u201319 July","author":"Kushik","year":"2013"},{"key":"2023091720460550600_ref13","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/11498490_2","volume-title":"Model-Based Testing of Reactive Systems","author":"Sandberg","year":"2005"},{"key":"2023091720460550600_ref14","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1016\/j.comnet.2004.09.009","article-title":"A passive testing approach based on invariants: application to the WAP","volume":"48","author":"Bayse","year":"2005","journal-title":"Comput. Netw."},{"key":"2023091720460550600_ref15","first-page":"215","volume-title":"International Conference on Implementation and Application of Automata (CIAA), Blois, France, 13\u201316 July","author":"Kushik","year":"2011"},{"key":"2023091720460550600_ref16","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-540-88282-4_4","volume-title":"International Conference on Language and Automata Theory and Applications, Tarragona, Spain, 13\u201319 March","author":"Volkov","year":"2008"},{"key":"2023091720460550600_ref17","first-page":"33","volume-title":"International Conference on Testing Software and Systems, Istanbul, Turkey, 13\u201315 November","author":"Kushik","year":"2013"},{"key":"2023091720460550600_ref18","first-page":"243","volume-title":"International Conference on Testing Software and Systems, Sharjah and Dubai, UAE, 23-25 November","author":"Kushik","year":"2015"},{"key":"2023091720460550600_ref19","first-page":"461","volume-title":"Proceedings of IEEE East-West Design and Test Symposium (EWDTS)","author":"Vinarskii","year":"2019"},{"key":"2023091720460550600_ref20","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1134\/S0361768814060140","article-title":"On the complexity of existence of homing sequences for nondeterministic finite state machines","volume":"40","author":"Kushik","year":"2014","journal-title":"Programm. Comput. Softw."},{"key":"2023091720460550600_ref21","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1007\/s10703-009-0065-1","article-title":"Conformance testing for real-time systems","volume":"34","author":"Krichen","year":"2009","journal-title":"Formal Methods Syst. Design"},{"key":"2023091720460550600_ref22","first-page":"66","volume-title":"Proc. of the 21st IFIP WG 6.1 Int. Conf. on Testing of Software and Communication Systems and 9th Int. FATES Workshop, Eindhoven, Netherlands, 2\u20134 November","author":"El-Fakih","year":"2009"},{"key":"2023091720460550600_ref23","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1016\/j.comnet.2007.10.002","article-title":"Formal testing from timed finite state machines","volume":"52","author":"Merayo","year":"2008","journal-title":"Comput. Netw."},{"key":"2023091720460550600_ref24","first-page":"203","volume-title":"Proceedings of International Conference GANDALF, Verona, Italy, 10\u201312 September","author":"Bresolin","year":"2014"},{"key":"2023091720460550600_ref25","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1007\/978-3-642-02138-1_9","volume-title":"International Conference on Formal Techniques for Distributed Systems, Lisboa, Portugal, 9\u201312 June","author":"Gromov","year":"2009"},{"key":"2023091720460550600_ref26","doi-asserted-by":"crossref","first-page":"376","DOI":"10.18255\/1818-1015-2020-4-376-395","article-title":"Deriving Homing Sequences for Finite State Machines with Timed Guards","volume":"27","author":"Tvardovskii","year":"2020","journal-title":"Model. Anal. Inf. Syst."},{"key":"2023091720460550600_ref27","doi-asserted-by":"crossref","DOI":"10.1007\/s11219-021-09548-z","article-title":"Evaluating the complexity of deriving adaptive S\u2019-homing and S\u2019-synchronizing sequences for nondeterministic FSMs","volume":"30","author":"Yevtushenko","year":"2022","journal-title":"Softw. Quality J"},{"key":"2023091720460550600_ref28","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1007\/978-3-030-31280-0_7","volume-title":"Proceedings of International Conference on Testing Software and Systems (ICTSS)","author":"Nguena","year":"2019"},{"key":"2023091720460550600_ref29","first-page":"315","article-title":"Searching for Optimal Homing Sequences for Testing Timed Communication Protocols","volume":"4","author":"Stulman","year":"2009","journal-title":"J. Netw."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2181\/51643505\/bxac069.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/9\/2181\/51643505\/bxac069.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,17]],"date-time":"2023-09-17T21:08:46Z","timestamp":1694984926000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/9\/2181\/6608475"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,15]]},"references-count":29,"journal-issue":{"issue":"9","published-online":{"date-parts":[[2022,6,15]]},"published-print":{"date-parts":[[2023,9,18]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxac069","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,9]]},"published":{"date-parts":[[2022,6,15]]}}}