{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T02:06:09Z","timestamp":1776305169082,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319694825","type":"print"},{"value":"9783319694832","type":"electronic"}],"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-69483-2_13","type":"book-chapter","created":{"date-parts":[[2017,10,16]],"date-time":"2017-10-16T07:34:48Z","timestamp":1508139288000},"page":"216-231","source":"Crossref","is-referenced-by-count":5,"title":["On Equivalence Checking of Nondeterministic Finite Automata"],"prefix":"10.1007","author":[{"given":"Chen","family":"Fu","sequence":"first","affiliation":[]},{"given":"Yuxin","family":"Deng","sequence":"additional","affiliation":[]},{"given":"David N.","family":"Jansen","sequence":"additional","affiliation":[]},{"given":"Lijun","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,10,17]]},"reference":[{"key":"13_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/978-3-540-78800-3_8","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"PA Abdulla","year":"2008","unstructured":"Abdulla, P.A., Bouajjani, A., Hol\u00edk, L., Kaati, L., Vojnar, T.: Computing Simulations over Tree Automata. In: Ramakrishnan, C.R., Rehof, J. (eds.) TACAS 2008. LNCS, vol. 4963, pp. 93\u2013108. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-78800-3_8"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"158","DOI":"10.1007\/978-3-642-12002-2_14","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"PA Abdulla","year":"2010","unstructured":"Abdulla, P.A., Chen, Y.-F., Hol\u00edk, L., Mayr, R., Vojnar, T.: When simulation meets antichains. In: Esparza, J., Majumdar, R. (eds.) TACAS 2010. LNCS, vol. 6015, pp. 158\u2013174. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-12002-2_14"},{"key":"13_CR3","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.-P.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Bonchi, F., Pous, D.: Checking NFA equivalence with bisimulations up to congruence. In: Principles of Programming Languages (POPL 2013), pp. 457\u2013468. ACM, New York (2013)","DOI":"10.1145\/2429069.2429124"},{"issue":"8","key":"13_CR5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"RE Bryant","year":"1986","unstructured":"Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput. 35(8), 677\u2013691 (1986). https:\/\/doi.org\/10.1109\/TC.1986.1676819","journal-title":"IEEE Trans. Comput."},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/11817963_5","volume-title":"Computer Aided Verification","author":"M Wulf De","year":"2006","unstructured":"De Wulf, M., Doyen, L., Henzinger, T.A., Raskin, J.-F.: Antichains: a new algorithm for checking universality of finite automata. In: Ball, T., Jones, R.B. (eds.) CAV 2006. LNCS, vol. 4144, pp. 17\u201330. Springer, Heidelberg (2006). doi: 10.1007\/11817963_5"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Henzinger, M.R., Henzinger, T.A., Kopke, P.W.: Computing simulations on finite and infinite graphs. In: Symposium on Foundations of Computer Science (FOCS), Milwaukee, pp. 453\u2013462. IEEE Computer Society (1995)","DOI":"10.1109\/SFCS.1995.492576"},{"issue":"6+","key":"13_CR8","first-page":"1337","volume":"29","author":"L Hol\u00edk","year":"2010","unstructured":"Hol\u00edk, L., \u0160im\u00e1\u010dek, J.: Optimizing an LTS-simulation algorithm. Comput. Inform. 29(6+), 1337\u20131348 (2010). http:\/\/www.cai.sk\/ojs\/index.php\/cai\/article\/view\/147","journal-title":"Comput. Inform."},{"key":"13_CR9","unstructured":"Hopcroft, J.E., Karp, R.M.: A linear algorithm for testing equivalence of finite automata. Technical report, 71\u2013114, Cornell University, Ithaca (1971). http:\/\/hdl.handle.net\/1813\/5958"},{"key":"13_CR10","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"Theory of Machines and Computations","author":"J Hopcroft","year":"1971","unstructured":"Hopcroft, J.: An $$n \\log n$$ algorithm for minimizing states in a finite automaton. In: Kohavi, Z., Paz, A. (eds.) Theory of Machines and Computations, pp. 189\u2013196. Academic Press, New York (1971)"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/978-3-642-28756-5_7","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"O Leng\u00e1l","year":"2012","unstructured":"Leng\u00e1l, O., \u0160im\u00e1\u010dek, J., Vojnar, T.: VATA: a library for efficient manipulation of non-deterministic tree automata. In: Flanagan, C., K\u00f6nig, B. (eds.) TACAS 2012. LNCS, vol. 7214, pp. 79\u201394. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-28756-5_7"},{"issue":"6","key":"13_CR12","doi-asserted-by":"crossref","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.E.: Three partition refinement algorithms. SIAM J. Comput. 16(6), 973\u2013989 (1987)","journal-title":"SIAM J. Comput."},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Pous, D.: Symbolic algorithms for language equivalence and Kleene algebra with tests. In: Principles of Programming Languages (POPL 2015), pp. 357\u2013368. ACM, New York (2015)","DOI":"10.1145\/2676726.2677007"},{"key":"13_CR14","doi-asserted-by":"crossref","unstructured":"Ranzato, F., Tapparo, F.: A new efficient simulation equivalence algorithm. In: Symposium on Logic in Computer Science (LICS), pp. 171\u2013180. IEEE Computer Society (2007)","DOI":"10.1109\/LICS.2007.8"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/BFb0055624","volume-title":"CONCUR\u201998 Concurrency Theory","author":"JJMM Rutten","year":"1998","unstructured":"Rutten, J.J.M.M.: Automata and coinduction (an exercise in coalgebra). In: Sangiorgi, D., de Simone, R. (eds.) CONCUR 1998. LNCS, vol. 1466, pp. 194\u2013218. Springer, Heidelberg (1998). doi: 10.1007\/BFb0055624"},{"key":"13_CR16","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time. In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing (STOC), pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"},{"key":"13_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11591191_28","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"D Tabakov","year":"2005","unstructured":"Tabakov, D., Vardi, M.Y.: Experimental evaluation of classical automata constructions. In: Sutcliffe, G., Voronkov, A. (eds.) LPAR 2005. LNCS, vol. 3835, pp. 396\u2013411. Springer, Heidelberg (2005). doi: 10.1007\/11591191_28"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1007\/978-3-642-02424-5_9","volume-title":"Applications and Theory of Petri Nets","author":"A Valmari","year":"2009","unstructured":"Valmari, A.: Bisimilarity minimization in O(m log n) time. In: Franceschinis, G., Wolf, K. (eds.) PETRI NETS 2009. LNCS, vol. 5606, pp. 123\u2013142. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-02424-5_9"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-642-39274-0_3","volume-title":"Implementation and Application of Automata","author":"M Veanes","year":"2013","unstructured":"Veanes, M.: Applications of symbolic finite automata. In: Konstantinidis, S. (ed.) CIAA 2013. LNCS, vol. 7982, pp. 16\u201323. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-39274-0_3"},{"key":"13_CR20","unstructured":"Whaley, J.: JavaBDD. http:\/\/javabdd.sourceforge.net\/ . Accessed 13 June 2017"}],"container-title":["Lecture Notes in Computer Science","Dependable Software Engineering. Theories, Tools, and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-69483-2_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T14:51:04Z","timestamp":1570200664000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-69483-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319694825","9783319694832"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-69483-2_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}