{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T06:54:39Z","timestamp":1763535279179},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,3,27]],"date-time":"2014-03-27T00:00:00Z","timestamp":1395878400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form Methods Syst Des"],"published-print":{"date-parts":[[2014,6]]},"DOI":"10.1007\/s10703-014-0205-0","type":"journal-article","created":{"date-parts":[[2014,3,26]],"date-time":"2014-03-26T20:30:06Z","timestamp":1395865806000},"page":"264-294","source":"Crossref","is-referenced-by-count":14,"title":["Hardness and inapproximability of minimizing adaptive distinguishing sequences"],"prefix":"10.1007","volume":"44","author":[{"given":"Uraz Cengiz","family":"T\u00fcrker","sequence":"first","affiliation":[]},{"given":"H\u00fcsn\u00fc","family":"Yenig\u00fcn","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,3,27]]},"reference":[{"key":"205_CR1","unstructured":"Adelson-Velskii G, Landis E (1962) An algorithm for the organization of information. In: Doklady Akademii Nauk USSR, vol 146, no 2, pp 263\u2013266"},{"key":"205_CR2","doi-asserted-by":"crossref","unstructured":"Adler M, Heeringa B (2008) Approximating optimal binary decision trees. In: Proceedings of the 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008 on approximation, randomization and combinatorial optimization: algorithms and techniques, Springer, Berlin, APPROX \u201908 \/ RANDOM \u201908, pp 1\u20139","DOI":"10.1007\/978-3-540-85363-3_1"},{"key":"205_CR3","doi-asserted-by":"crossref","unstructured":"Aho AV, Dahbura AT, Lee D, Uyar M\u00dc (1991) An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. IEEE Trans Commun 39(11):1604\u20131615. doi: 10.1109\/26.111442","DOI":"10.1109\/26.111442"},{"key":"205_CR4","doi-asserted-by":"crossref","unstructured":"Alur R, Courcoubetis C, Yannakakis M (1995) Distinguishing tests for nondeterministic and probabilistic machines. In: Leighton FT, Borodin A (eds) Proceedings of the twenty-seventh annual ACM symposium on theory of computing. ACM, Las Vegas, Nevada, USA, STOC\u201995, pp 363\u2013372, 29 May\u20131 June 1995. doi: 10.1145\/225058.225161","DOI":"10.1145\/225058.225161"},{"key":"205_CR5","doi-asserted-by":"crossref","unstructured":"Betin-Can A, Bultan T (2004) Verifiable concurrent programming using concurrency controllers. In: Proceedings of the 19th IEEE international conference on automated software engineering, IEEE Computer Society, pp 248\u2013257","DOI":"10.1109\/ASE.2004.1342742"},{"key":"205_CR6","volume-title":"Testing object-oriented systems: models, patterns, and tools","author":"RV Binder","year":"1999","unstructured":"Binder RV (1999) Testing object-oriented systems: models, patterns, and tools. Addison-Wesley, Reading"},{"key":"205_CR7","doi-asserted-by":"crossref","unstructured":"Bochmann G, Petrenko A (1994) Protocol testing: review of methods and relevance for software testing. In: ACM international symposium on software testing and analysis, Seattle, USA, pp 109\u2013123","DOI":"10.1145\/186258.187153"},{"key":"205_CR8","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1109\/T-C.1974.224043","volume":"23","author":"RT Boute","year":"1974","unstructured":"Boute RT (1974) Distinguishing sets for optimal state identification in checking experiments. IEEE Trans Comput 23:874\u2013877","journal-title":"IEEE Trans Comput"},{"key":"205_CR9","unstructured":"Brglez F (1996) ACM\/SIGMOD benchmark dataset. Available online at http:\/\/www.cbl.ncsu.edu\/benchmarks\/Benchmarks-upto-1996.html . Accessed 13 Feb 2014"},{"key":"205_CR10","unstructured":"Brinksma E (1988) A theory for the derivation of tests. In: Proceedings of protocol specification, testing, and verification VIII, North-Holland, Atlantic City, pp 63\u201374"},{"key":"205_CR11","doi-asserted-by":"crossref","unstructured":"Broy M, Jonsson B, Katoen JP, Leucker M, Pretschner A (eds) (2005) Model-based testing of reactive systems: advanced lectures. In: Lecture notes in Computer Science, vol 3472. Springer, Berlin","DOI":"10.1007\/b137241"},{"key":"205_CR12","doi-asserted-by":"crossref","unstructured":"Chakaravarthy VT, Pandit V, Roy S, Awasthi P, Mohania M (2007) Decision trees for entity identification: approximation algorithms and hardness results. In: Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on principles of database systems, ACM, PODS \u201907, pp 53\u201362","DOI":"10.1145\/1265530.1265538"},{"issue":"2","key":"205_CR13","doi-asserted-by":"crossref","first-page":"15:1","DOI":"10.1145\/1921659.1921661","volume":"7","author":"VT Chakaravarthy","year":"2011","unstructured":"Chakaravarthy VT, Pandit V, Roy S, Awasthi P, Mohania MK (2011) Decision trees for entity identification: approximation algorithms and hardness results. ACM Trans Algorithms 7(2):15:1\u201315:22. doi: 10.1145\/1921659.1921661","journal-title":"ACM Trans Algorithms"},{"issue":"4","key":"205_CR14","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/75247.75274","volume":"19","author":"WYL Chan","year":"1989","unstructured":"Chan WYL, Vuong CT, Otp MR (1989) An improved protocol test generation procedure based on UIOS. SIGCOMM Comput Commun Rev 19(4):283\u2013294. doi: 10.1145\/75247.75274","journal-title":"SIGCOMM Comput Commun Rev"},{"key":"205_CR15","doi-asserted-by":"crossref","unstructured":"Chen J, Hierons R, Ural H, Yenigun H (2005) Eliminating redundant tests in a checking sequence. In: Khendek F, Dssouli R (eds) Testing of communicating systems. Lecture notes in Computer Science, vol 3502. Springer, Berlin, pp 371\u2013371. doi: 10.1007\/11430230_11","DOI":"10.1007\/11430230_11"},{"key":"205_CR16","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TSE.1978.231496","volume":"4","author":"TS Chow","year":"1978","unstructured":"Chow TS (1978) Testing software design modelled by finite state machines. IEEE Trans Softw Eng 4:178\u2013187","journal-title":"IEEE Trans Softw Eng"},{"key":"205_CR17","unstructured":"da Silva Sim\u00e3o A, Petrenko A (2008) Generating checking sequences for partial reduced finite state machines. In: TestCom\/FATES, pp 153\u2013168"},{"issue":"8","key":"205_CR18","doi-asserted-by":"crossref","first-page":"1023","DOI":"10.1109\/TC.2010.17","volume":"59","author":"A Silva Sim\u00e3o da","year":"2010","unstructured":"da Silva Sim\u00e3o A, Petrenko A (2010) Checking completeness of tests for finite state machines. IEEE Trans Comput 59(8):1023\u20131032","journal-title":"IEEE Trans Comput"},{"issue":"6","key":"205_CR19","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1002\/stvr.452","volume":"22","author":"A Silva Sim\u00e3o da","year":"2012","unstructured":"da Silva Sim\u00e3o A, Petrenko A, Yevtushenko N (2012) On reducing test length for fsms with extra states. Softw Test Verif Reliab 22(6):435\u2013454","journal-title":"Softw Test Verif Reliab"},{"issue":"8","key":"205_CR20","doi-asserted-by":"crossref","first-page":"1317","DOI":"10.1109\/5.58319","volume":"78","author":"A Dahbura","year":"1990","unstructured":"Dahbura A, Sabnani K, Uyar M (1990) Formal methods for generating protocol conformance test sequences. Proc IEEE 78(8):1317\u20131326","journal-title":"Proc IEEE"},{"key":"205_CR21","unstructured":"Din\u00e7t\u00fcrk ME (2009) A two phase approach for checking sequence generation. Master\u2019s thesis, Sabanci University"},{"issue":"12","key":"205_CR22","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 AR, Yevtushenko N (2010) FSM-based conformance testing methods: a survey annotated with experimental evaluation. Inf Softw Technol 52(12):1286\u20131297. doi: 10.1016\/j.infsof.2010.07.001","journal-title":"Inf Softw Technol"},{"issue":"3","key":"205_CR23","doi-asserted-by":"crossref","first-page":"500","DOI":"10.1137\/0219033","volume":"19","author":"D Eppstein","year":"1990","unstructured":"Eppstein D (1990) Reset sequences for monotonic automata. SIAM J Comput 19(3):500\u2013510","journal-title":"SIAM J Comput"},{"key":"205_CR24","volume-title":"Fault detection in digital circuits. Computer applications in electrical engineering series","author":"A Friedman","year":"1971","unstructured":"Friedman A, Menon P (1971) Fault detection in digital circuits. Computer applications in electrical engineering series. Prentice-Hall, Englewood Cliffs"},{"issue":"6","key":"205_CR25","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1109\/32.87284","volume":"17","author":"S Fujiwara","year":"1991","unstructured":"Fujiwara S, v Bochmann G, Khendek F, Amalou M, Ghedamsi A (1991) Test selection based on finite state models. IEEE Trans Softw Eng 17(6):591\u2013603","journal-title":"IEEE Trans Softw Eng"},{"key":"205_CR26","volume-title":"Computers and intractability","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability. W. H. Freeman and Company, New York"},{"key":"205_CR27","volume-title":"Introduction to the theory of finite state machines","author":"A Gill","year":"1962","unstructured":"Gill A (1962) Introduction to the theory of finite state machines. McGraw-Hill, New York"},{"key":"205_CR28","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1109\/T-C.1970.222975","volume":"19","author":"G Gonenc","year":"1970","unstructured":"Gonenc G (1970) A method for the design of fault detection experiments. IEEE Trans Comput 19:551\u2013558","journal-title":"IEEE Trans Comput"},{"key":"205_CR29","doi-asserted-by":"crossref","unstructured":"G\u00fcni\u00e7en C, T\u00fcrker UC, Ural H, Yeni\u00fcn H (2011) Generating preset distinguishing sequences using SAT. In: Gelenbe E, Lent R, Sakellari G (eds) Proceedings of 26th international symposium on Computer and information sciences II. Springer, London, UK, ISCIS \u201911, p 487\u2013493, 26\u201328 Sept 2011. doi: 10.1007\/978-1-4471-2155-8_62","DOI":"10.1007\/978-1-4471-2155-8_62"},{"key":"205_CR30","doi-asserted-by":"crossref","unstructured":"Haydar M, Petrenko A, Sahraoui H (2004) Formal verification of web applications modeled by communicating automata. In: Formal techniques for networked and distributed systems (FORTE 2004), Springer Lecture Notes in Computer Science, vol 3235. Springer, Madrid, pp 115\u2013132","DOI":"10.1007\/978-3-540-30232-2_8"},{"key":"205_CR31","doi-asserted-by":"crossref","unstructured":"Hennie FC (1964) Fault-detecting experiments for sequential circuits. In: Proceedings of fifth annual symposium on switching circuit theory and logical design, Princeton, NJ, pp 95\u2013110","DOI":"10.1109\/SWCT.1964.8"},{"issue":"9","key":"205_CR32","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1109\/TC.2002.1032630","volume":"51","author":"RM Hierons","year":"2002","unstructured":"Hierons RM, Ural H (2002) Reduced length checking sequences. IEEE Trans Comput 51(9):1111\u20131117","journal-title":"IEEE Trans Comput"},{"key":"205_CR33","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1109\/TC.2006.80","volume":"55","author":"RM Hierons","year":"2006","unstructured":"Hierons RM, Ural H (2006) Optimizing the length of checking sequences. IEEE Trans Comput 55:618\u2013629","journal-title":"IEEE Trans Comput"},{"key":"205_CR34","doi-asserted-by":"crossref","unstructured":"Hierons RM, Jourdan GV, Ural H, Yenigun H (2009) Checking sequence construction using adaptive and preset distinguishing sequences. In: Proceedings of the 2009 seventh IEEE international conference on software engineering and formal methods, IEEE Computer Society, Washington, DC, USA, SEFM \u201909, pp 157\u2013166. doi: 10.1109\/SEFM.2009.12","DOI":"10.1109\/SEFM.2009.12"},{"key":"205_CR35","volume-title":"Design and validation of computer protocols. Prentice-Hall software series","author":"GJ Holzmann","year":"1991","unstructured":"Holzmann GJ (1991) Design and validation of computer protocols. Prentice-Hall software series. Prentice Hall, Englewood Cliffs"},{"key":"205_CR36","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"The theory of machines and computation","author":"JE Hopcroft","year":"1971","unstructured":"Hopcroft JE (1971) An n log n algorithm for minimizing the states in a finite automaton. In: Kohavi Z (ed) The theory of machines and computation. Academic Press, New York, pp 189\u2013196"},{"key":"205_CR37","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0020-0190(76)90095-8","volume":"5","author":"L Hyafil","year":"1976","unstructured":"Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-complete. Inf Process Lett 5:15\u201317","journal-title":"Inf Process Lett"},{"issue":"6","key":"205_CR38","doi-asserted-by":"crossref","first-page":"667","DOI":"10.1007\/s00165-009-0135-6","volume":"22","author":"GV Jourdan","year":"2010","unstructured":"Jourdan GV, Ural H, Yenigun H, Zhang J (2010) Lower bounds on lengths of checking sequences. Form Asp Comput 22(6):667\u2013679","journal-title":"Form Asp Comput"},{"key":"205_CR39","volume-title":"Switching and finite state Automata theory","author":"Z Kohavi","year":"1978","unstructured":"Kohavi Z (1978) Switching and finite state Automata theory. McGraw-Hill, New York"},{"key":"205_CR40","doi-asserted-by":"crossref","unstructured":"Kushik N, El-Fakih K, Yevtushenko N (2013) Adaptive homing and distinguishing experiments for nondeterministic finite state machines. In: Yenigun H, Yilmaz C, Ulrich A (eds) Testing software and systems. Lecture Notes in Computer Science, vol 8254. Springer, Berlin, pp 33\u201348","DOI":"10.1007\/978-3-642-41707-8_3"},{"issue":"1\u20132","key":"205_CR41","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.dam.2004.06.002","volume":"144","author":"ES Laber","year":"2004","unstructured":"Laber ES, Nogueira LT (2004) On the hardness of the minimum height decision tree problem. Discret Appl Math 144(1\u20132):209\u2013212. doi: 10.1016\/j.dam.2004.06.002","journal-title":"Discret Appl Math"},{"issue":"1","key":"205_CR42","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0164-1212(01)00132-7","volume":"62","author":"R Lai","year":"2002","unstructured":"Lai R (2002) A survey of communication protocol testing. J Syst Softw 62(1):21\u201346. doi: 10.1016\/S0164-1212(01)00132-7","journal-title":"J Syst Softw"},{"issue":"3","key":"205_CR43","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1109\/12.272431","volume":"43","author":"D Lee","year":"1994","unstructured":"Lee D, Yannakakis M (1994) Testing finite-state machines: state identification and verification. IEEE Trans Comput 43(3):306\u2013320","journal-title":"IEEE Trans Comput"},{"issue":"8","key":"205_CR44","doi-asserted-by":"crossref","first-page":"1089","DOI":"10.1109\/JPROC.1996.533955","volume":"84","author":"D Lee","year":"1996","unstructured":"Lee D, Yannakakis M (1996) Principles and methods of testing finite-state machines\u2014a survey. Proc IEEE 84(8):1089\u20131123","journal-title":"Proc IEEE"},{"issue":"5","key":"205_CR45","doi-asserted-by":"crossref","first-page":"631","DOI":"10.1109\/26.494307","volume":"44","author":"D Lee","year":"1996","unstructured":"Lee D, Sabnani K, Kristol D, Paul S (1996) Conformance testing of protocols specified as communicating finite state machines-a guided random walk based approach. IEEE Trans Commun 44(5):631\u2013640. doi: 10.1109\/26.494307","journal-title":"IEEE Trans Commun"},{"key":"205_CR46","doi-asserted-by":"crossref","unstructured":"Low S (1993) Probabilistic conformance testing of protocols with unobservable transitions. In: Proceedings of the international conference on network protocols, pp 368\u2013375. doi: 10.1109\/ICNP.1993.340890","DOI":"10.1109\/ICNP.1993.340890"},{"key":"205_CR47","doi-asserted-by":"crossref","unstructured":"Mihail M, Papadimitriou CH (1994) On the random walk method for protocol testing. In: Proceedings of computer-aided verification (CAV 1994). Lecture notes in Computer Science, vol 818. Springer, Berlin, pp 132\u2013141","DOI":"10.1007\/3-540-58179-0_49"},{"key":"205_CR48","volume-title":"Automata studies","author":"EP Moore","year":"1956","unstructured":"Moore EP (1956) Gedanken-experiments. In: Shannon C, McCarthy J (eds) Automata studies. Princeton University Press, Princeton"},{"issue":"9","key":"205_CR49","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1109\/TC.2005.152","volume":"54","author":"A Petrenko","year":"2005","unstructured":"Petrenko A, Yevtushenko N (2005) Testing from partial deterministic FSM specifications. IEEE Trans Comput 54(9):1154\u20131165","journal-title":"IEEE Trans Comput"},{"issue":"7","key":"205_CR50","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1109\/12.599899","volume":"46","author":"I Pomeranz","year":"1997","unstructured":"Pomeranz I, Reddy SM (1997) Test generation for multiple state-table faults in finite-state machines. IEEE Trans Comput 46(7):783\u2013794","journal-title":"IEEE Trans Comput"},{"issue":"4","key":"205_CR51","first-page":"285","volume":"15","author":"K Sabnani","year":"1988","unstructured":"Sabnani K, Dahbura A (1988) A protocol test generation procedure. Comput Netw 15(4):285\u2013297","journal-title":"Comput Netw"},{"issue":"4","key":"205_CR52","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1109\/32.16602","volume":"15","author":"DP Sidhu","year":"1989","unstructured":"Sidhu DP, Leung TK (1989) Formal methods for protocol testing: a detailed study. IEEE Trans Softw Eng 15(4):413\u2013426","journal-title":"IEEE Trans Softw Eng"},{"key":"205_CR53","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1007\/BF01068822","volume":"7","author":"MN Sokolovskii","year":"1971","unstructured":"Sokolovskii MN (1971) Diagnostic experiments with automata. Cybern Syst Anal 7:988\u2013994. doi: 10.1007\/BF01068822","journal-title":"Cybern Syst Anal"},{"key":"205_CR54","unstructured":"Stowell S (2012) Instant R: an introduction to R for statistical analysis. Jotunheim Publishing. URL http:\/\/www.instantr.com\/book"},{"key":"205_CR55","unstructured":"Teetor P (2011) R Cookbook, 1st edn. O\u2019Reilly. URL http:\/\/oreilly.com\/catalog\/9780596809157"},{"key":"205_CR56","doi-asserted-by":"crossref","unstructured":"T\u00fcrker UC, Yenig\u00fcn H (2012) Hardness and inapproximability results for minimum verification set and minimum path decision tree problems. Technical Report 19826, Sabanc\u0131 University, Istanbul, Turkey. URL http:\/\/research.sabanciuniv.edu\/19826\/","DOI":"10.5900\/SU_FENS_WP.2012.19826"},{"issue":"3","key":"205_CR57","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1109\/90.234857","volume":"1","author":"H Ural","year":"1993","unstructured":"Ural H, Zhu K (1993) Optimal length test sequence generation using distinguishing sequences. IEEE\/ACM Trans Netw 1(3):358\u2013371","journal-title":"IEEE\/ACM Trans Netw"},{"issue":"1","key":"205_CR58","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1109\/12.559807","volume":"46","author":"H Ural","year":"1997","unstructured":"Ural H, Wu X, Zhang F (1997) On minimizing the lengths of checking sequences. IEEE Trans Comput 46(1):93\u201399","journal-title":"IEEE Trans Comput"},{"issue":"5","key":"205_CR59","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1002\/stvr.456","volume":"22","author":"M Utting","year":"2012","unstructured":"Utting M, Pretschner A, Legeard B (2012) A taxonomy of model-based testing approaches. Softw Test Verif Reliab 22(5):297\u2013312","journal-title":"Softw Test Verif Reliab"},{"key":"205_CR60","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1007\/BF01068590","volume":"9","author":"MP Vasilevskii","year":"1973","unstructured":"Vasilevskii MP (1973) Failure diagnosis of automata. Cybern Sys Anal 9:653\u2013665. doi: 10.1007\/BF01068590","journal-title":"Cybern Sys Anal"},{"key":"205_CR61","unstructured":"Vuong ST, Chan WWL, Ito MR (1989) The UIOv-method for protocol test sequence generation. In: The 2nd international workshop on protocol test systems, Berlin"}],"container-title":["Formal Methods in System Design"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-014-0205-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10703-014-0205-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10703-014-0205-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T02:09:40Z","timestamp":1648692580000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10703-014-0205-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,3,27]]},"references-count":61,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6]]}},"alternative-id":["205"],"URL":"https:\/\/doi.org\/10.1007\/s10703-014-0205-0","relation":{},"ISSN":["0925-9856","1572-8102"],"issn-type":[{"value":"0925-9856","type":"print"},{"value":"1572-8102","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,3,27]]}}}