{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T10:38:58Z","timestamp":1725878338886},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319519623"},{"type":"electronic","value":"9783319519630"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-51963-0_12","type":"book-chapter","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T06:17:39Z","timestamp":1484029059000},"page":"147-160","source":"Crossref","is-referenced-by-count":3,"title":["Hardness of Deriving Invertible Sequences from Finite State Machines"],"prefix":"10.1007","author":[{"given":"Robert M.","family":"Hierons","sequence":"first","affiliation":[]},{"given":"Mohammad Reza","family":"Mousavi","sequence":"additional","affiliation":[]},{"given":"Michael Kirkedal","family":"Thomsen","sequence":"additional","affiliation":[]},{"given":"Uraz Cengiz","family":"T\u00fcrker","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,11]]},"reference":[{"key":"12_CR1","unstructured":"Moore, E.P.: Gedanken-experiments. In: Shannon, C., McCarthy, J. (eds.) Automata Studies. Princeton University Press (1956)"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Hennie, F.C.: Fault-detecting experiments for sequential circuits. In: Proceedings of Fifth Annual Symposium on Switching Circuit Theory and Logical Design, Princeton, New Jersey, pp. 95\u2013110, November 1964","DOI":"10.1109\/SWCT.1964.8"},{"issue":"11","key":"12_CR3","doi-asserted-by":"crossref","first-page":"1604","DOI":"10.1109\/26.111442","volume":"39","author":"AV 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. Commun. 39(11), 1604\u20131615 (1991)","journal-title":"IEEE Trans. Commun."},{"key":"12_CR4","doi-asserted-by":"crossref","first-page":"178","DOI":"10.1109\/TSE.1978.231496","volume":"4","author":"TS Chow","year":"1978","unstructured":"Chow, T.S.: Testing software design modelled by finite state machines. IEEE Trans. Soft. Eng. 4, 178\u2013187 (1978)","journal-title":"IEEE Trans. Soft. Eng."},{"issue":"3","key":"12_CR5","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s10515-009-0061-0","volume":"17","author":"RM Hierons","year":"2010","unstructured":"Hierons, R.M., Ural, H.: Generating a checking sequence with a minimum number of reset transitions. Autom. Softw. Eng. 17(3), 217\u2013250 (2010)","journal-title":"Autom. Softw. Eng."},{"issue":"3","key":"12_CR6","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1109\/90.234857","volume":"1","author":"H Ural","year":"1993","unstructured":"Ural, H., Zhu, K.: Optimal length test sequence generation using distinguishing sequences. IEEE\/ACM Trans. Network. 1(3), 358\u2013371 (1993)","journal-title":"IEEE\/ACM Trans. Network."},{"issue":"2","key":"12_CR7","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1109\/32.265636","volume":"20","author":"GL Luo","year":"1994","unstructured":"Luo, G.L., von Bochmann, G., Petrenko, A.: Test selection based on communicating nondeterministic finite-state machines using a generalized Wp-method. IEEE Trans. Softw. Eng. 20(2), 149\u2013161 (1994)","journal-title":"IEEE Trans. Softw. Eng."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Petrenko, A., Yevtushenko, N., von Bochmann, G.: Testing deterministic implementations from nondeterministic FSM specifications. In: Baumgarten, B., Burkhardt, H.-J., Giessler, A. (eds.) IFIP TC6 9th International Workshop on Testing of Communicating Systems, Darmstadt, Germany, 9\u201311 September 1996, pp. 125\u2013141. Chapman and Hall (1996)","DOI":"10.1007\/978-0-387-35062-2_10"},{"key":"12_CR9","volume-title":"Introduction to The Theory of Finite State Machines","author":"A Gill","year":"1962","unstructured":"Gill, A.: Introduction to The Theory of Finite State Machines. McGraw-Hill, New York (1962)"},{"key":"12_CR10","volume-title":"Switching and Finite State Automata Theory","author":"Z Kohavi","year":"1978","unstructured":"Kohavi, Z.: Switching and Finite State Automata Theory. McGraw-Hill, New York (1978)"},{"key":"12_CR11","doi-asserted-by":"crossref","first-page":"874","DOI":"10.1109\/T-C.1974.224043","volume":"23","author":"RT Boute","year":"1974","unstructured":"Boute, R.T.: Distinguishing sets for optimal state identification in checking experiments. IEEE Trans. Comput. 23, 874\u2013877 (1974)","journal-title":"IEEE Trans. Comput."},{"issue":"1","key":"12_CR12","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.: On minimizing the lengths of checking sequences. IEEE Trans. Comput. 46(1), 93\u201399 (1997)","journal-title":"IEEE Trans. Comput."},{"key":"12_CR13","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. In: Protocol Specification, Testing, and Verification VIII, pp. 75\u201386. Elsevier (North-Holland), Atlantic City (1988)"},{"issue":"4","key":"12_CR14","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1145\/75247.75274","volume":"19","author":"WYL Chan","year":"1989","unstructured":"Chan, W.Y.L., Vuong, C.T., Otp, M.R.: An improved protocol test generation procedure based on UIOs. SIGCOMM Comput. Commun. Rev. 19(4), 283\u2013294 (1989)","journal-title":"SIGCOMM Comput. Commun. Rev."},{"issue":"2","key":"12_CR15","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1109\/90.374116","volume":"3","author":"W-H Chen","year":"1995","unstructured":"Chen, W.-H., Ural, H.: Synchronizable test sequences based on multiple UIO sequence. IEEE\/ACM Trans. Netw. 3(2), 152\u2013157 (1995)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Guyot, S., Ural, H.: Synchronizable checking sequences based on UIO sequences. In: Protocol Test Systems, VIII, Evry, France, September 1995, pp. 385\u2013397. Chapman and Hall (1995)","DOI":"10.1007\/978-0-387-34988-6_25"},{"key":"12_CR17","unstructured":"Motteler, H., Chung, A., Sidhu, D.: Fault coverage of UIO-based methods for protocol testing. In: Proceedings of Protocol Test Systems VI, pp. 21\u201333 (1994)"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Ramalingam, T., Thulasiraman, K., Das, A.: A generalization of the multiple UIO method of test sequence selection for protocols represented in FSM. In: The 7th International workshop on Protocol Test Systems, Japan, pp. 209\u2013224. Chapman and Hall (1994)","DOI":"10.1007\/978-0-387-34883-4_14"},{"issue":"10","key":"12_CR19","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1016\/0140-3664(93)90082-4","volume":"16","author":"H Ural","year":"1993","unstructured":"Ural, H., Wang, Z.: Synchronizable test sequence generation using UIO sequences. Comput. Commun. 16(10), 653\u2013661 (1993)","journal-title":"Comput. Commun."},{"key":"12_CR20","unstructured":"Vuong, S.T., Chan, W.W.L., Ito, M.R.: The UIOv-method for protocol test sequence generation. In: The 2nd International Workshop on Protocol Test Systems, Berlin (1989)"},{"issue":"3","key":"12_CR21","doi-asserted-by":"crossref","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. Comput. 43(3), 306\u2013320 (1994)","journal-title":"IEEE Trans. Comput."},{"key":"12_CR22","first-page":"653","volume":"4","author":"MP Vasilevskii","year":"1973","unstructured":"Vasilevskii, M.P.: Failure diagnosis of automata. Cybernetics 4, 653\u2013665 (1973)","journal-title":"Cybernetics"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Hierons, R.M., T\u00fcrker, U.C.: Parallel algorithms for generating harmonised state identifiers, characterising sets (accepted). IEEE Trans. Softw. Eng. (2016)","DOI":"10.1109\/TC.2016.2532869"},{"key":"12_CR24","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1109\/T-C.1970.222975","volume":"19","author":"G Gonenc","year":"1970","unstructured":"Gonenc, G.: A method for the design of fault detection experiments. IEEE Trans. Comput. 19, 551\u2013558 (1970)","journal-title":"IEEE Trans. Comput."},{"key":"12_CR25","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1109\/TC.2006.80","volume":"55","author":"RM Hierons","year":"2006","unstructured":"Hierons, R.M., Ural, H.: Optimizing the length of checking sequences. IEEE Trans. Comput. 55, 618\u2013629 (2006)","journal-title":"IEEE Trans. Comput."},{"issue":"9","key":"12_CR26","doi-asserted-by":"crossref","first-page":"1111","DOI":"10.1109\/TC.2002.1032630","volume":"51","author":"RM Hierons","year":"2002","unstructured":"Hierons, R.M., Ural, H.: Reduced length checking sequences. IEEE Trans. Comput. 51(9), 1111\u20131117 (2002)","journal-title":"IEEE Trans. Comput."},{"issue":"4","key":"12_CR27","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1093\/comjnl\/39.4.325","volume":"39","author":"RM Hierons","year":"1996","unstructured":"Hierons, R.M.: Extending test sequence overlap by invertibility. Comput. J. 39(4), 325\u2013330 (1996)","journal-title":"Comput. J."},{"issue":"4","key":"12_CR28","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/90.649519","volume":"5","author":"K Naik","year":"1997","unstructured":"Naik, K.: Efficient computation of unique input\/output sequences in finite-state machines. IEEE\/ACM Trans. Netw. 5(4), 585\u2013599 (1997)","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"12_CR29","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, J.E.: An n log n algorithm for minimizing the states in a finite automaton. In: Kohavi, Z. (ed.) The Theory of Machines and Computation, pp. 189\u2013196. Academic Press, New York (1971)"},{"key":"12_CR30","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability. W.H. Freeman and Company, New York (1979)"},{"key":"12_CR31","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proceedings of the 18th Annual Symposium on Foundations of Computer Science, SFCS 1977, pp. 254\u2013266. IEEE Computer Society, Washington (1977)","DOI":"10.1109\/SFCS.1977.16"},{"issue":"2","key":"12_CR32","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2017: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-51963-0_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T10:03:10Z","timestamp":1568714590000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-51963-0_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319519623","9783319519630"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-51963-0_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}