{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:38:13Z","timestamp":1740109093080,"version":"3.37.3"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2018,3,1]],"date-time":"2018-03-01T00:00:00Z","timestamp":1519862400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002724","name":"American University of Sharjah","doi-asserted-by":"crossref","award":["AUS FRG-15-R27"],"award-info":[{"award-number":["AUS FRG-15-R27"]}],"id":[{"id":"10.13039\/501100002724","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"crossref","award":["#16-49-03012"],"award-info":[{"award-number":["#16-49-03012"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2018,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>\n            A top-down approach is presented for checking the existence and derivation of an adaptive distinguishing test case (called also an adaptive distinguishing sequence) for a nondeterministic finite state machine (NDFSM). When such a test case exists, the method returns a canonical test case that includes all other distinguishing tests of the given complete observable NDFSM. In the second part of the paper, a constructive approach is provided for deriving a class of complete observable NDFSMs with\n            <jats:italic>n<\/jats:italic>\n            states,\n            <jats:italic>n<\/jats:italic>\n            &gt;\u00a0 2, and 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2212\n            <jats:italic>n<\/jats:italic>\n            \u2212 1 inputs such that a shortest adaptive distinguishing test case for each NDFSM in the intended class has the length (height) 2\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            \u2212\n            <jats:italic>n<\/jats:italic>\n            \u2212 1. In other words, we prove the reachability of the exponential upper bound on the length of a shortest adaptive distinguishing sequence for complete observable NDFSMs while for deterministic machines the upper bound is polynomial with respect to the number of states. For constructing the intended class of NDFSMs for a given\n            <jats:italic>n<\/jats:italic>\n            , we propose a special linear order over all the non-empty subsets without singletons of an\n            <jats:italic>n<\/jats:italic>\n            -element set. The obtained tight exponential upper bound initiates further research on identifying certain NDFSM classes where this upper bound is not reachable.\n          <\/jats:p>","DOI":"10.1007\/s00165-017-0450-2","type":"journal-article","created":{"date-parts":[[2018,1,26]],"date-time":"2018-01-26T10:32:02Z","timestamp":1516962722000},"page":"319-332","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Adaptive distinguishing test cases of nondeterministic finite state machines: test case derivation and length estimation"],"prefix":"10.1145","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2343-2848","authenticated-orcid":false,"given":"Khaled","family":"El-Fakih","sequence":"first","affiliation":[{"name":"American University of Sharjah, PO Box 26666, Sharjah, United Arab Emirates"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nina","family":"Yevtushenko","sequence":"additional","affiliation":[{"name":"Tomsk State University, Tomsk, Russia"},{"name":"Institute for System Programming RAS, Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalia","family":"Kushik","sequence":"additional","affiliation":[{"name":"SAMOVAR, CNRS, T\u00e9l\u00e9com SudParis, Universit\u00e9 Paris-Saclay, \u00c9vry, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","unstructured":"Alur R Courcoubetis C Yannakakis M (1995) Distinguishing tests for nondeterministic and probabilistic machines In: Proceedings of the 27th ACM symposium on theory of computing pp 363\u2013372","DOI":"10.1145\/225058.225161"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"crossref","unstructured":"Bochmann GV Petrenko A (1994) Protocol testing: review of methods and relevance for software testing In: Proceedings of international symposium on software testing and analysis Seattle pp 109\u2013123","DOI":"10.1145\/186258.187153"},{"key":"e_1_2_1_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(61)80003-X"},{"key":"e_1_2_1_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2010.07.001"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-014-0297-8"},{"key":"e_1_2_1_2_6_2","doi-asserted-by":"crossref","unstructured":"G\u00fcni\u00e7en C Jourdan G-V Yenig\u00fcn H (2015) Using multiple adaptive distinguishing sequences for checking sequence gen eration. In: Proceedings of the 27th international conference on testing software and systems ICTSS 2015 Lecture notes in computer science 9447 Springer pp 19\u201334","DOI":"10.1007\/978-3-319-25945-1_2"},{"key":"e_1_2_1_2_7_2","doi-asserted-by":"crossref","unstructured":"Hierons RM T\u00fcrker UC (2014) Distinguishing sequences for partially specified FSMs. In: Proceedings of NASA formal methods of the 6th international symposium (NFM 2014) Houston TX USA April 29-May 1 2014 pp 62\u201376","DOI":"10.1007\/978-3-319-06200-6_5"},{"volume-title":"Switching and finite automata theory","year":"1978","author":"Kohavi Z","key":"e_1_2_1_2_8_2"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"crossref","unstructured":"Kushik N El-Fakih K Yevtushenko N (2011) 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","DOI":"10.1007\/978-3-642-22256-6_20"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-014-0357-7"},{"issue":"3","key":"e_1_2_1_2_11_2","first-page":"306","article-title":"finite-statemachines: state identification and verification","volume":"43","author":"Lee D","year":"1994","journal-title":"IEEETransComput"},{"key":"e_1_2_1_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/5.533956"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/1816865"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"crossref","unstructured":"Petrenko A Yevtushenko N (2011) Adaptive testing of deterministic implementations specified by nondeterministic FSMs. Lecture notes in computer science vol 7019 pp 162\u2013178","DOI":"10.1007\/978-3-642-24580-0_12"},{"key":"e_1_2_1_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/1324162.1324165"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-014-0205-0"},{"key":"e_1_2_1_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.infsof.2016.02.001"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.asoc.2016.07.019"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-017-0450-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-017-0450-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-017-0450-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-017-0450-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,7]],"date-time":"2022-01-07T06:54:40Z","timestamp":1641538480000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-017-0450-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["10.1007\/s00165-017-0450-2"],"URL":"https:\/\/doi.org\/10.1007\/s00165-017-0450-2","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"type":"print","value":"0934-5043"},{"type":"electronic","value":"1433-299X"}],"subject":[],"published":{"date-parts":[[2018,3]]},"assertion":[{"value":"14 January 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 December 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}