Độ khó và tính không xấp xỉ của việc tối thiểu hóa các chuỗi phân biệt thích ứng

Adelson-Velskii G, Landis E (1962) An algorithm for the organization of information. In: Doklady Akademii Nauk USSR, vol 146, no 2, pp 263–266 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 ’08 / RANDOM ’08, pp 1–9 Aho AV, Dahbura AT, Lee D, Uyar MÜ (1991) An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. IEEE Trans Commun 39(11):1604–1615. doi:10.1109/26.111442 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’95, pp 363–372, 29 May–1 June 1995. doi:10.1145/225058.225161 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–257 Binder RV (1999) Testing object-oriented systems: models, patterns, and tools. Addison-Wesley, Reading 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–123 Boute RT (1974) Distinguishing sets for optimal state identification in checking experiments. IEEE Trans Comput 23:874–877 Brglez F (1996) ACM/SIGMOD benchmark dataset. Available online at http://www.cbl.ncsu.edu/benchmarks/Benchmarks-upto-1996.html. Accessed 13 Feb 2014 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–74 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 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 ’07, pp 53–62 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–15:22. doi:10.1145/1921659.1921661 Chan WYL, Vuong CT, Otp MR (1989) An improved protocol test generation procedure based on UIOS. SIGCOMM Comput Commun Rev 19(4):283–294. doi:10.1145/75247.75274 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–371. doi:10.1007/11430230_11 Chow TS (1978) Testing software design modelled by finite state machines. IEEE Trans Softw Eng 4:178–187 da Silva Simão A, Petrenko A (2008) Generating checking sequences for partial reduced finite state machines. In: TestCom/FATES, pp 153–168 da Silva Simão A, Petrenko A (2010) Checking completeness of tests for finite state machines. IEEE Trans Comput 59(8):1023–1032 da Silva Simão A, Petrenko A, Yevtushenko N (2012) On reducing test length for fsms with extra states. Softw Test Verif Reliab 22(6):435–454 Dahbura A, Sabnani K, Uyar M (1990) Formal methods for generating protocol conformance test sequences. Proc IEEE 78(8):1317–1326 Dinçtürk ME (2009) A two phase approach for checking sequence generation. Master’s thesis, Sabanci University 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–1297. doi:10.1016/j.infsof.2010.07.001 Eppstein D (1990) Reset sequences for monotonic automata. SIAM J Comput 19(3):500–510 Friedman A, Menon P (1971) Fault detection in digital circuits. Computer applications in electrical engineering series. Prentice-Hall, Englewood Cliffs 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–603 Garey MR, Johnson DS (1979) Computers and intractability. W. H. Freeman and Company, New York Gill A (1962) Introduction to the theory of finite state machines. McGraw-Hill, New York Gonenc G (1970) A method for the design of fault detection experiments. IEEE Trans Comput 19:551–558 Güniçen C, Türker UC, Ural H, Yeniün 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 ’11, p 487–493, 26–28 Sept 2011. doi:10.1007/978-1-4471-2155-8_62 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–132 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–110 Hierons RM, Ural H (2002) Reduced length checking sequences. IEEE Trans Comput 51(9):1111–1117 Hierons RM, Ural H (2006) Optimizing the length of checking sequences. IEEE Trans Comput 55:618–629 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 ’09, pp 157–166. doi:10.1109/SEFM.2009.12 Holzmann GJ (1991) Design and validation of computer protocols. Prentice-Hall software series. Prentice Hall, Englewood Cliffs 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–196 Hyafil L, Rivest RL (1976) Constructing optimal binary decision trees is NP-complete. Inf Process Lett 5:15–17 Jourdan GV, Ural H, Yenigun H, Zhang J (2010) Lower bounds on lengths of checking sequences. Form Asp Comput 22(6):667–679 Kohavi Z (1978) Switching and finite state Automata theory. McGraw-Hill, New York 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–48 Laber ES, Nogueira LT (2004) On the hardness of the minimum height decision tree problem. Discret Appl Math 144(1–2):209–212. doi:10.1016/j.dam.2004.06.002 Lai R (2002) A survey of communication protocol testing. J Syst Softw 62(1):21–46. doi:10.1016/S0164-1212(01)00132-7 Lee D, Yannakakis M (1994) Testing finite-state machines: state identification and verification. IEEE Trans Comput 43(3):306–320 Lee D, Yannakakis M (1996) Principles and methods of testing finite-state machines—a survey. Proc IEEE 84(8):1089–1123 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–640. doi:10.1109/26.494307 Low S (1993) Probabilistic conformance testing of protocols with unobservable transitions. In: Proceedings of the international conference on network protocols, pp 368–375. doi:10.1109/ICNP.1993.340890 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–141 Moore EP (1956) Gedanken-experiments. In: Shannon C, McCarthy J (eds) Automata studies. Princeton University Press, Princeton Petrenko A, Yevtushenko N (2005) Testing from partial deterministic FSM specifications. IEEE Trans Comput 54(9):1154–1165 Pomeranz I, Reddy SM (1997) Test generation for multiple state-table faults in finite-state machines. IEEE Trans Comput 46(7):783–794 Sabnani K, Dahbura A (1988) A protocol test generation procedure. Comput Netw 15(4):285–297 Sidhu DP, Leung TK (1989) Formal methods for protocol testing: a detailed study. IEEE Trans Softw Eng 15(4):413–426 Sokolovskii MN (1971) Diagnostic experiments with automata. Cybern Syst Anal 7:988–994. doi:10.1007/BF01068822 Stowell S (2012) Instant R: an introduction to R for statistical analysis. Jotunheim Publishing. URL http://www.instantr.com/book Teetor P (2011) R Cookbook, 1st edn. O’Reilly. URL http://oreilly.com/catalog/9780596809157 Türker UC, Yenigün H (2012) Hardness and inapproximability results for minimum verification set and minimum path decision tree problems. Technical Report 19826, Sabancı University, Istanbul, Turkey. URL http://research.sabanciuniv.edu/19826/ Ural H, Zhu K (1993) Optimal length test sequence generation using distinguishing sequences. IEEE/ACM Trans Netw 1(3):358–371 Ural H, Wu X, Zhang F (1997) On minimizing the lengths of checking sequences. IEEE Trans Comput 46(1):93–99 Utting M, Pretschner A, Legeard B (2012) A taxonomy of model-based testing approaches. Softw Test Verif Reliab 22(5):297–312 Vasilevskii MP (1973) Failure diagnosis of automata. Cybern Sys Anal 9:653–665. doi:10.1007/BF01068590 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