{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T17:05:16Z","timestamp":1790355916633,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_6","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"28-45","source":"Crossref","is-referenced-by-count":13,"title":["Testing, Optimizaton, and Games"],"prefix":"10.1007","author":[{"given":"Mihalis","family":"Yannakakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"11","key":"6_CR1","doi-asserted-by":"publisher","first-page":"1604","DOI":"10.1109\/26.111442","volume":"39","author":"A.V. Aho","year":"1991","unstructured":"Aho, A.V., Dahbura, A.T., Lee, D., Uyar, M.U.: An optimization technique for protocol conformance test generation based on UIO sequences and rural Chinese postman tours. IEEE Trans. on Communication\u00a039(11), 1604\u20131615 (1991)","journal-title":"IEEE Trans. on Communication"},{"key":"6_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Courcoubetis, C., Yannakakis, M.: Distinguishing tests for nondeterministic and probabilistic machines. In: Proc. 27th Ann. ACM Symp. on Theory of Computing, pp. 363\u2013372 (1995)","DOI":"10.1145\/225058.225161"},{"issue":"3","key":"6_CR3","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1145\/503502.503503","volume":"23","author":"R. Alur","year":"2001","unstructured":"Alur, R., Yannakakis, M.: Model checking of hierarchical state machines. ACM Trans. on Progr. Languages and Systems\u00a023(3), 273\u2013303 (2001)","journal-title":"ACM Trans. on Progr. Languages and Systems"},{"key":"6_CR4","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples. Inform. and Comp.\u00a075, 87\u2013106 (1987)","journal-title":"Inform. and Comp."},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Apfelbaum, L.: Automated functional test generation. In: Proc. IEEE Autotestcon Conference (1995)","DOI":"10.1109\/AUTEST.1995.522660"},{"key":"6_CR6","volume-title":"Unified Modeling Language User Guide","author":"G. Booch","year":"1997","unstructured":"Booch, G., Jacobson, I., Rumbaugh, J.: Unified Modeling Language User Guide. Addison-Wesley, Reading (1997)"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1007\/3-540-45510-8_9","volume-title":"Modeling and Verification of Parallel Processes","author":"E. Brinksma","year":"2001","unstructured":"Brinksma, E., Tretmans, J.: Testing transition systems: An annotated bibliography. In: Cassez, F., Jard, C., Rozoy, B., Dermot, M. (eds.) MOVEP 2000. LNCS, vol.\u00a02067, pp. 187\u2013195. Springer, Heidelberg (2001)"},{"issue":"3","key":"6_CR8","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1109\/TSE.1978.231496","volume":"SE-4","author":"T.S. Chow","year":"1978","unstructured":"Chow, T.S.: Testing software design modeled by finite-state machines. IEEE Trans. on Software Engineering\u00a0SE-4(3), 178\u2013187 (1978)","journal-title":"IEEE Trans. on Software Engineering"},{"key":"6_CR9","volume-title":"Model Checking","author":"E.M. Clarke","year":"2000","unstructured":"Clarke, E.M., Grumberg, O., Peled, D.: Model Checking. MIT Press, Cambridge (2000)"},{"key":"6_CR10","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/BF01580113","volume":"5","author":"J. Edmonds","year":"1973","unstructured":"Edmonds, J., Johnson, E.L.: Matching, Euler tours and the Chinese postman. Mathematical Programming\u00a05, 88\u2013124 (1973)","journal-title":"Mathematical Programming"},{"key":"6_CR11","first-page":"53","volume-title":"Proc. IFIP Joint Intl. Conf. FORTE XIII-PSTV XX","author":"K. Etessami","year":"2000","unstructured":"Etessami, K., Yannakakis, M.: From Rule-Based to Automata-Based Testing. In: Proc. IFIP Joint Intl. Conf. FORTE XIII-PSTV XX, pp. 53\u201368. Kluwer, Dordrecht (2000)"},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Friedman, G., Hartman, A., Nagin, K., Shiran, T.: Projected state machine coverage for software testing. In: Proc. ISSTA (2002)","DOI":"10.1145\/566172.566192"},{"key":"6_CR13","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A. Frieze","year":"1982","unstructured":"Frieze, A., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks\u00a012, 23\u201339 (1982)","journal-title":"Networks"},{"key":"6_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/3-540-46002-0_25","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"A. Groce","year":"2002","unstructured":"Groce, A., Peled, D., Yannakakis, M.: Adaptive model checking. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol.\u00a02280, pp. 357\u2013370. Springer, Heidelberg (2002)"},{"key":"6_CR15","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/0167-6423(87)90035-9","volume":"8","author":"D. Harel","year":"1987","unstructured":"Harel, D.: Statecharts: A visual formalism for complex systems. Science of Computer Programming\u00a08, 231\u2013274 (1987)","journal-title":"Science of Computer Programming"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Hennie, F.C.: Fault detection experiments for sequential circuits. In: Proc. 5th Annual Symp. Switching Circuit Theory and Logical Design, pp. 95\u2013110 (1964)","DOI":"10.1109\/SWCT.1964.8"},{"key":"6_CR17","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1002\/bltj.2034","volume":"2","author":"G. Holzmann","year":"1997","unstructured":"Holzmann, G., Peled, D.A., Redberg, M.H.: Design tools for requirements engineering. Bell Labs Technical Journal\u00a02, 86\u201395 (1997)","journal-title":"Bell Labs Technical Journal"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/3-540-46002-0_23","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"H.S. Hong","year":"2002","unstructured":"Hong, H.S., Lee, I., Sokolsky, O., Ural, H.: A temporal logic based theory of test coverage and generation. In: Katoen, J.-P., Stevens, P. (eds.) TACAS 2002. LNCS, vol.\u00a02280, pp. 327\u2013341. Springer, Heidelberg (2002)"},{"key":"6_CR19","doi-asserted-by":"crossref","unstructured":"Lee, D., Yannakakis, M.: On-line minimization of transition systems. In: Proc. 24th Ann. ACM Symp. on Theory of Computing, pp. 264\u2013274 (1992)","DOI":"10.1145\/129712.129738"},{"issue":"3","key":"6_CR20","doi-asserted-by":"publisher","first-page":"306","DOI":"10.1109\/12.272431","volume":"43","author":"D. Lee","year":"1994","unstructured":"Lee, D., Yannakakis, M.: Testing finite state machines: state identification and verification. IEEE Trans. on Computers\u00a043(3), 306\u2013320 (1994)","journal-title":"IEEE Trans. on Computers"},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Lee, D., Yannakakis, M.: Optimization problems from feature testing of communication protocols. In: Proc. Intl. Conf. on Network Protocols, pp. 66\u201375 (1996)","DOI":"10.1109\/ICNP.1996.564905"},{"issue":"8","key":"6_CR22","doi-asserted-by":"publisher","first-page":"1090","DOI":"10.1109\/5.533956","volume":"84","author":"D. Lee","year":"1996","unstructured":"Lee, D., Yannakakis, M.: Principles and methods of testing finite state machines - a survey. Proc. of IEEE\u00a084(8), 1090\u20131123 (1996)","journal-title":"Proc. of IEEE"},{"key":"6_CR23","series-title":"Automata Studies, Annals of Mathematics Studies","first-page":"129","volume-title":"Gedanken-experiments on sequential machines","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F.: Gedanken-experiments on sequential machines. Automata Studies, Annals of Mathematics Studies, vol.\u00a034, pp. 129\u2013153. Princeton University Press, Princeton (1956)"},{"key":"6_CR24","unstructured":"Mosk-Aoyama, D., Yannakakis, M.: Testing Hierarchical Systems via Edge Covering (2004) (manuscript)"},{"key":"6_CR25","first-page":"238","volume-title":"Proc. IEEE Fault Tolerant Comput. Symp.","author":"S. Naito","year":"1981","unstructured":"Naito, S., Tsunoyama, M.: Fault detection for sequential machines by transitions tours. In: Proc. IEEE Fault Tolerant Comput. Symp., pp. 238\u2013243. IEEE Computer Society Press, Los Alamitos (1981)"},{"issue":"2","key":"6_CR26","first-page":"225","volume":"7","author":"D. Peled","year":"2002","unstructured":"Peled, D., Vardi, M., Yannakakis, M.: Black box checking. Journal of Automata, Languages and Combinatorics\u00a07(2), 225\u2013246 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/3-540-45510-8_10","volume-title":"Modeling and Verification of Parallel Processes","author":"A. Petrenko","year":"2001","unstructured":"Petrenko, A.: Fault model-driven test derivation from finite state models: Annotated bibliography. In: Cassez, F., Jard, C., Rozoy, B., Dermot, M. (eds.) MOVEP 2000. LNCS, vol.\u00a02067, pp. 196\u2013205. Springer, Heidelberg (2001)"},{"key":"6_CR28","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(84)90034-5","volume":"29","author":"J. Reif","year":"1984","unstructured":"Reif, J.: The complexity of two-player games with incomplete information. J. Computer and System Sciences\u00a029, 274\u2013301 (1984)","journal-title":"J. Computer and System Sciences"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Rivest, R.L., Schapire, R.E.: Inference of finite automata using homing sequences. In: Proc. 21st Ann. Symp. on Theory of Computing, pp. 411\u2013420 (1989)","DOI":"10.1145\/73007.73047"},{"issue":"3","key":"6_CR30","first-page":"103","volume":"17","author":"J. Tretmans","year":"1996","unstructured":"Tretmans, J.: Test generation with inputs, outputs amd repetitive quiescence. Software - Concepts and Tools\u00a017(3), 103\u2013120 (1996)","journal-title":"Software - Concepts and Tools"},{"key":"6_CR31","unstructured":"http:\/\/cm.bell-labs.com\/cm\/cs\/what\/ubet"},{"key":"6_CR32","first-page":"98","volume":"4","author":"M.P. Vasilevskii","year":"1973","unstructured":"Vasilevskii, M.P.: Failure diagnosis of automata. Kibernetika\u00a0(4), 98\u2013108 (1973)","journal-title":"Kibernetika"},{"issue":"2","key":"6_CR33","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1006\/jcss.1995.1019","volume":"50","author":"M. Yannakakis","year":"1995","unstructured":"Yannakakis, M., Lee, D.: Testing finite state machines: fault detection. J. of Computer and System Sciences\u00a050(2), 209\u2013227 (1995)","journal-title":"J. of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:24:01Z","timestamp":1605741841000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}