{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:50:27Z","timestamp":1763535027640},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2010,11,1]],"date-time":"2010-11-01T00:00:00Z","timestamp":1288569600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2010,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Lower bounds on the lengths of checking sequences constructed for testing from Finite State Machine-based specifications are established. These bounds consider the case where a distinguishing sequence is used in forming state recognition and transition verification subsequences and identify the effects of overlapping among such subsequences. Empirical results show that the existing methods for construction of checking sequences provide checking sequences with lengths that are within acceptable distance to these lower bounds.<\/jats:p>","DOI":"10.1007\/s00165-009-0135-6","type":"journal-article","created":{"date-parts":[[2009,11,18]],"date-time":"2009-11-18T23:39:43Z","timestamp":1258587583000},"page":"667-679","source":"Crossref","is-referenced-by-count":14,"title":["Lower bounds on lengths of checking sequences"],"prefix":"10.1145","volume":"22","author":[{"given":"Guy-Vincent","family":"Jourdan","sequence":"first","affiliation":[{"name":"SITE, University of Ottawa, K1N 6N5, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hasan","family":"Ural","sequence":"additional","affiliation":[{"name":"SITE, University of Ottawa, K1N 6N5, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00fcsn\u00fc","family":"Yenig\u00fcn","sequence":"additional","affiliation":[{"name":"FENS, Sabanci University, 34956, Istanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji Chao","family":"Zhang","sequence":"additional","affiliation":[{"name":"SITE, University of Ottawa, K1N 6N5, Ottawa, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"publisher","DOI":"10.1109\/26.111442"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"crossref","unstructured":"Barnett M Grieskamp W Nachmanson L Schulte W Tillmann N Veanes M (2003) Towards a tool environment for model-based testing with AsmL. In: Proceedings of FATES\u201903 Springer-Verlag lecture notes in computer science 2931:252\u2013266","DOI":"10.1007\/978-3-540-24617-6_18"},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/338330"},{"key":"e_1_2_1_2_4_2","volume-title":"Testing embedded software","author":"Broekman B","year":"2003"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"crossref","unstructured":"Chen J Hierons RM Ural H Yenigun H (2005) Eliminating redundant tests in checking sequences. In: Proceedings of IFIP TestCom\u201905 Montreal Quebec pp 146\u2013158","DOI":"10.1007\/11430230_11"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.1978.231496"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2007.70707"},{"key":"e_1_2_1_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2004.1275300"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.58319"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1147\/sj.411.0089"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.87284"},{"issue":"3","key":"e_1_2_1_2_12_2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/stvr.402","article-title":"Testing with model checkers: a survey","volume":"19","author":"Fraser G","year":"2009","journal-title":"J Softw Test Verif Reliab"},{"key":"e_1_2_1_2_13_2","volume-title":"Introduction to the theory of finite-state machines","author":"Gill A","year":"1962"},{"issue":"4","key":"e_1_2_1_2_14_2","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1002\/stvr.340","article-title":"Integration testing of object-oriented components using finite state machines","volume":"16","author":"Gallagher L","year":"2006","journal-title":"J Softw Testing Verif Reliab"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1970.222975"},{"issue":"1","key":"e_1_2_1_2_16_2","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1002\/stvr.352","article-title":"Heuristics for fault diagnosing when testing from finite state machines","volume":"17","author":"Guo Q","year":"2007","journal-title":"J Softw Testing Verif Reliab"},{"key":"e_1_2_1_2_17_2","doi-asserted-by":"crossref","unstructured":"Hennie FC (1964) Fault detecting experiments for sequential circuits. In Proceedings of the 5th symposium switching circuit theory and logical design pp 95\u2013110 Princeton","DOI":"10.1109\/SWCT.1964.8"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10515-006-7739-3"},{"key":"e_1_2_1_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/39.4.325"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1538942.1538944"},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1032630"},{"key":"e_1_2_1_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.80"},{"key":"e_1_2_1_2_23_2","doi-asserted-by":"crossref","unstructured":"Haydar M Petrenko A Sahraoui H (2004) Formal verification of web applications modeled by communicating automata. In: Proceedings of the FORTE 2004 Springer-Verlag lecture notes in computer science 3235:115\u2013132","DOI":"10.1007\/978-3-540-30232-2_8"},{"key":"e_1_2_1_2_24_2","first-page":"232","article-title":"Data flow testing as model checking","volume":"03","author":"Hong HS","year":"2003","journal-title":"In: Proceedings of the international conference software engineering ICSE\u2019"},{"key":"e_1_2_1_2_25_2","volume-title":"Switching and finite state automata theory","author":"Kohavi Z","year":"1978"},{"key":"e_1_2_1_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.272431"},{"key":"e_1_2_1_2_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.533956"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.222912"},{"key":"e_1_2_1_2_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2004.1265734"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0169-7552(88)90064-5"},{"key":"e_1_2_1_2_31_2","doi-asserted-by":"crossref","unstructured":"Sim\u00e3o A Petrenko A (2008) Generating checking sequences for partial reduced finite state machines. In: Proceedings of the IFIP TestCom\u201908 Tokyo Japan pp 153\u2013168","DOI":"10.1007\/978-3-540-68524-1_12"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"crossref","unstructured":"Tekle KT Ural H Yalcin CM Yenigun H (2005) Generalizing redundancy elimination in checking sequences. In: Proceedings of the ISCIS\u201905 Istanbul Turkey pp 915\u2013926","DOI":"10.1007\/11569596_93"},{"key":"e_1_2_1_2_33_2","doi-asserted-by":"crossref","unstructured":"Ural H Zhang F (2006) Reducing the lengths of checking sequences by overlapping. In: Proceedings of the IFIP TestCom\u201906 New York pp 274\u2013288","DOI":"10.1007\/11754008_18"},{"key":"e_1_2_1_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.234857"},{"key":"e_1_2_1_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/12.559807"},{"key":"e_1_2_1_2_36_2","doi-asserted-by":"crossref","unstructured":"Yang B Ural H (1990) Protocol conformance test generation using multiple UIO sequences with overlapping. In: Proceedings of the ACM SIGCOMM 90: communications architectures and protocols Twente The Netherlands pp 118\u2013125","DOI":"10.1145\/99508.99543"},{"key":"e_1_2_1_2_37_2","unstructured":"Zhang JC (2006) Effect of overlapping on checking sequence generation. M.Sc. Thesis University of Ottawa October 2006 Ottawa Canada"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-009-0135-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-009-0135-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-009-0135-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,6]],"date-time":"2022-01-06T15:52:43Z","timestamp":1641484363000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-009-0135-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,11]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["10.1007\/s00165-009-0135-6"],"URL":"https:\/\/doi.org\/10.1007\/s00165-009-0135-6","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,11]]}}}