{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:00:31Z","timestamp":1725516031927},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540708438"},{"type":"electronic","value":"9783540708445"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70844-5_9","type":"book-chapter","created":{"date-parts":[[2008,7,22]],"date-time":"2008-07-22T09:19:29Z","timestamp":1216718369000},"page":"78-91","source":"Crossref","is-referenced-by-count":1,"title":["Hopcroft\u2019s Minimization Technique: Queues or Stacks?"],"prefix":"10.1007","author":[{"given":"Andrei","family":"P\u0103un","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mihaela","family":"P\u0103un","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alfonso","family":"Rodr\u00edguez-Pat\u00f3n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/11812128_12","volume-title":"Implementation and Application of Automata","author":"M. Baclet","year":"2006","unstructured":"Baclet, M., Pagetti, C.: Around Hopcroft\u2019s Algorithm. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol.\u00a04094, pp. 114\u2013125. Springer, Heidelberg (2006)"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Berstel, J., Carton, O.: On the complexity of Hopcrofts state minimization algorithm. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 35\u201344. Springer, Heidelberg (2005)","DOI":"10.1007\/978-3-540-30500-2_4"},{"key":"9_CR3","first-page":"758","volume":"49","author":"N.G. Bruijn de","year":"1946","unstructured":"de Bruijn, N.G.: A Combinatorial Problem. Koninklijke Nederlandse Akademie v. Wetenschappen\u00a049, 758\u2013764 (1946)","journal-title":"Koninklijke Nederlandse Akademie v. Wetenschappen"},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1142\/S0129054102000960","volume":"13","author":"C. C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., P\u0103un, A., Yu, S.: An Efficient Algorithm for Constructing Minimal Cover Automata for Finite Languages. International Journal of Foundations of Computer Science\u00a013(1), 83\u201397 (2002)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"3","key":"9_CR5","first-page":"303","volume":"7","author":"C. C\u00e2mpeanu","year":"2002","unstructured":"C\u00e2mpeanu, C., Salomaa, K., Yu, S.: Tight Lower Bound for the State Complexity of Shuffle of Regular Languages. Journal of Automata, Languages and Combinatorics\u00a07(3), 303\u2013310 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/3-540-48057-9_4","volume-title":"Automata Implementation","author":"C. C\u00e2mpeanu","year":"1999","unstructured":"C\u00e2mpeanu, C., S\u00e2ntean, N., Yu, S.: Minimal Cover-Automata for Finite Languages. In: Champarnaud, J.-M., Maurel, D., Ziadi, D. (eds.) WIA 1998. LNCS, vol.\u00a01660, pp. 32\u201342. Springer, Heidelberg (1999); Theoretical Computer Science 267, 3\u201316 (2001)"},{"key":"9_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-48057-9","volume-title":"Automata Implementation","author":"J.M. Champarnaud","year":"1999","unstructured":"Champarnaud, J.M., Maurel, D.: Automata Implementation. In: Champarnaud, J.-M., Maurel, D., Ziadi, D. (eds.) WIA 1998. LNCS, vol.\u00a01660. Springer, Heidelberg (1999)"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-46011-X_28","volume-title":"Developments in Language Theory","author":"M. Domaratzki","year":"2002","unstructured":"Domaratzki, M., Shallit, J., Yu, S.: Minimal Covers of Formal Languages. In: Kuich, W., Rozenberg, G., Salomaa, A. (eds.) DLT 2001. LNCS, vol.\u00a02295, pp. 319\u2013329. Springer, Heidelberg (2002)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF00264025","volume":"2","author":"D. Gries","year":"1973","unstructured":"Gries, D.: Describing an algorithm by Hopcroft. Acta Informatica\u00a02, 97\u2013109 (1973)","journal-title":"Acta Informatica"},{"key":"9_CR10","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"J.E. Hopcroft","year":"2001","unstructured":"Hopcroft, J.E., Ullman, J.D., Motwani, R.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (2001)"},{"key":"9_CR11","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.E. Hopcroft","year":"1971","unstructured":"Hopcroft, J.E.: 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, London (1971)"},{"issue":"1","key":"9_CR12","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/S0890-5401(03)00090-7","volume":"186","author":"L. Ilie","year":"2003","unstructured":"Ilie, L., Yu, S.: Follow automata. Inf. Comput.\u00a0186(1), 140\u2013162 (2003)","journal-title":"Inf. Comput."},{"issue":"1-2","key":"9_CR13","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/S0304-3975(99)00150-4","volume":"250","author":"T. Knuutila","year":"2001","unstructured":"Knuutila, T.: Re-describing an algorithm by Hopcroft. Theoretical Computer Science\u00a0250(1-2), 333\u2013363 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"9_CR14","doi-asserted-by":"publisher","first-page":"1071","DOI":"10.1142\/S0129054103002187","volume":"14","author":"H. K\u00f6rner","year":"2003","unstructured":"K\u00f6rner, H.: A Time and Space Efficient Algorithm for Minimizing Cover Automata for Finite Languages. International Journal of Foundations of Computer Science\u00a014(6), 1071\u20131086 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"9_CR15","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0304-3975(85)90159-8","volume":"40","author":"R. Paige","year":"1985","unstructured":"Paige, R., Tarjan, R.E., Bonic, R.: A Linear Time Solution to the Single Function Coarsest Partition Problem. Theoretical Computer Science\u00a040, 67\u201384 (1985)","journal-title":"Theoretical Computer Science"},{"key":"9_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/3-540-44674-5_20","volume-title":"Implementation and Application of Automata","author":"A. P\u0103un","year":"2001","unstructured":"P\u0103un, A., Santean, N., Yu, S.: An O(n 2) Algorithm for Constructing Minimal Cover Automata for Finite Languages. In: Yu, S., P\u0103un, A. (eds.) CIAA 2000. LNCS, vol.\u00a02088, pp. 243\u2013251. Springer, Heidelberg (2001)"},{"key":"9_CR17","volume-title":"Formal Languages","author":"A. Salomaa","year":"1973","unstructured":"Salomaa, A.: Formal Languages. Academic Press, London (1973)"},{"issue":"1","key":"9_CR18","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/S0304-3975(99)00020-1","volume":"231","author":"K. Salomaa","year":"2000","unstructured":"Salomaa, K., Wu, X., Yu, S.: Efficient Implementation of Regular Languages Using Reversed Alternating Finite Automata. Theor. Comput. Sci.\u00a0231(1), 103\u2013111 (2000)","journal-title":"Theor. Comput. Sci."},{"key":"9_CR19","unstructured":"S\u00e2ntean, N.: Towards a Minimal Representation for Finite Languages: Theory and Practice. MSc Thesis, Department of Computer Science, The University of Western Ontario (2000)"},{"key":"9_CR20","first-page":"41","volume-title":"Handbook of Formal Languages","author":"S. Yu","year":"1998","unstructured":"Yu, S.: Regular Languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 41\u2013110. Springer, Heidelberg (1998)"},{"key":"9_CR21","first-page":"142","volume":"76","author":"S. Yu","year":"2002","unstructured":"Yu, S.: State Complexity of Finite and Infinite Regular Languages. Bulletin of the EATCS\u00a076, 142\u2013152 (2002)","journal-title":"Bulletin of the EATCS"},{"issue":"1-4","key":"9_CR22","first-page":"471","volume":"64","author":"S. Yu","year":"2005","unstructured":"Yu, S.: State Complexity: Recent Results and Open Problems. Fundam. Inform.\u00a064(1-4), 471\u2013480 (2005)","journal-title":"Fundam. Inform."},{"key":"9_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/11812128_3","volume-title":"Implementation and Application of Automata","author":"S. Yu","year":"2006","unstructured":"Yu, S.: On the State Complexity of Combined Operations. In: Ibarra, O.H., Yen, H.-C. (eds.) CIAA 2006. LNCS, vol.\u00a04094, pp. 11\u201322. Springer, Heidelberg (2006)"},{"key":"9_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0031375","volume-title":"Proceedings of Second International Workshop on Implementing Automata","author":"D. Wood","year":"1998","unstructured":"Wood, D., Yu, S.: Automata Implementation. In: Proceedings of Second International Workshop on Implementing Automata. LNCS, vol.\u00a01436. Springer, Heidelberg (1998)"},{"key":"9_CR25","unstructured":"The Grail + Project. A symbolic computation environment for finite state machines, regular expressions, and finite languages, http:\/\/www.csd.uwo.ca\/research\/grail\/"}],"container-title":["Lecture Notes in Computer Science","Implementation and Applications of Automata"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70844-5_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:30:19Z","timestamp":1620016219000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70844-5_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540708438","9783540708445"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70844-5_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}