{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:33:03Z","timestamp":1725492783705},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540440406"},{"type":"electronic","value":"9783540456872"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45687-2_27","type":"book-chapter","created":{"date-parts":[[2007,10,19]],"date-time":"2007-10-19T08:57:47Z","timestamp":1192784267000},"page":"328-340","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Algorithms for Computing Small NFAs"],"prefix":"10.1007","author":[{"given":"Lucian","family":"Iliea","sequence":"first","affiliation":[]},{"given":"Sheng","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,10,4]]},"reference":[{"volume-title":"Compilers: Principles, Techniques, and Tools","year":"1988","author":"A. Aho","key":"27_CR1","unstructured":"Aho, A., Sethi, R., Ullman, J., Compilers: Principles, Techniques, and Tools, Addison-Wesley, MA, 1988."},{"key":"27_CR2","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1016\/0304-3975(95)00182-4","volume":"155","author":"V. Antimirov","year":"1996","unstructured":"Antimirov, V., Partial derivatives of regular expressions and finite automaton constructions, Theoret. Comput. Sci.\n 155 (1996) 291\u2013319.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0304-3975(86)90088-5","volume":"48","author":"G. Berry","year":"1986","unstructured":"Berry, G, Sethi, R., From regular expressions to deterministic automata, Theoret. Comput. Sci.\n 48 (1986) 117\u2013126.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR4","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/0304-3975(93)90287-4","volume":"120","author":"A. Br\u00fcggemann-Klein","year":"1993","unstructured":"Br\u00fcggemann-Klein, A., Regular expressions into finite automata, Theoret. Comput. Sci.\n 120(1993) 197\u2013213.","journal-title":"Theoret. Comput. Sci."},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1145\/321239.321249","volume":"11","author":"J. Brzozowski","year":"1964","unstructured":"Brzozowski, J., Derivatives of regular expressions, J. ACM\n 11 (1964) 481\u2013494.","journal-title":"J. ACM"},{"key":"27_CR6","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1007\/3-540-44674-5_7","volume-title":"Proc. of CIAA 2000","author":"J.-M. Champarnaud","year":"2001","unstructured":"Champarnaud, J.-M., Ziadi, D., New finite automaton constructions based on canonical derivatives, in: S. Yu, A. Paun, eds., Proc. of CIAA 2000, Lecture Notes in Comput. Sci. 2088, Springer-Verlag, Berlin, 2001, 94\u2013104."},{"key":"27_CR7","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/3-540-48194-X_15","volume-title":"Proc. of 12th CPM","author":"J.-M. Champarnaud","year":"2001","unstructured":"Champarnaud, J.-M., Ziadi, D., Computing the equation automaton of a regular expression in $$\n\\mathcal{O}\n$$\nspace and time, in: A. Amir, G. Landau, Proc. of 12th CPM, Lecture Notes in Comput. Sci. 2089, Springer-Verlag, Berlin, 2001, 157\u2013168."},{"key":"27_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(96)00140-5","volume":"178","author":"C.-H. Chang","year":"1997","unstructured":"Chang, C.-H., Paige, R., From regular expressions to DFA\u2019s using compressed NFA\u2019s, Theoret. Comput. Sci\n 178 (1997) 1\u201336.","journal-title":"Theoret. Comput. Sci"},{"key":"27_CR9","unstructured":"Friedl, J., Mastering Regular Expressions, O\u2019Reilly, 1998."},{"key":"27_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1070\/RM1961v016n05ABEH004112","volume":"16","author":"V.M. Glushkov","year":"1961","unstructured":"Glushkov, V.M., The abstract theory of automata, Russian Math. Surveys 16 (1961) 1\u201353.","journal-title":"Russian Math. Surveys"},{"issue":"4","key":"27_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1051\/ita:2000116","volume":"34","author":"C. Hagenah","year":"2000","unstructured":"Hagenah, C., Muscholl, A., Computing \u03b5-free NFA from regular expressions in O(n log2(n)) time, Theor. Inform. Appl.\n 34(4) (2000) 257\u2013277.","journal-title":"Theor. Inform. Appl."},{"key":"27_CR12","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/B978-0-12-417750-5.50022-1","volume-title":"Proc. Internat. Sympos. 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, Proc. Internat. Sympos. Theory of machines and computations, Technion, Haifa, 1971, Academic Press, New York, 1971, 189\u2013196."},{"volume-title":"Introduction to Automata Theory, Languages, and Computation","year":"1979","author":"J.E. Hopcroft","key":"27_CR13","unstructured":"Hopcroft, J.E., Ullman, J.D., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, Mass., 1979."},{"issue":"4","key":"27_CR14","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J. Hromkovic","year":"2001","unstructured":"Hromkovic, J., Seibert, S., Wilke, T., Translating regular expressions into small \u03b5-free nondeterministic finite automata, J. Comput. System Sci.\n 62(4) (2001) 565\u2013588.","journal-title":"J. Comput. System Sci."},{"key":"27_CR15","series-title":"Lect Notes Comput Sci","volume-title":"Proc. of 13th CPM","author":"L. Ilie","year":"2002","unstructured":"Ilie, L., Yu, S., Constructing NFAs by optimal use of positions in regular expressions, in: A. Apostolico, M. Takeda, Proc. of 13th CPM, Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, 2002, to appear."},{"issue":"1","key":"27_CR16","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/TEC.1960.5221603","volume":"9","author":"R. McNaughton","year":"1960","unstructured":"McNaughton, R., Yamada, H., Regular expressions and state graphs for automata, IEEE Trans. on Electronic Computers\n 9(1) (1960) 39\u201347.","journal-title":"IEEE Trans. on Electronic Computers"},{"volume-title":"EATCS Monographs on Theoretical Computer Science","year":"1988","author":"S. Sippu","key":"27_CR17","unstructured":"Sippu, S., Soisalon-Soininen, E., Parsing Theory: I Languages and Parsing, EATCS Monographs on Theoretical Computer Science, Vol. 15, Springer-Verlag, New York, 1988."},{"issue":"6","key":"27_CR18","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"Thompson, K., Regular expression search algorithm, Comm. ACM\n 11(6) (1968) 419\u2013422.","journal-title":"Comm. ACM"},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages, Vol. I","author":"S. Yu","year":"1997","unstructured":"Yu, S., Regular Languages, in: G. Rozenberg, A. Salomaa, Handbook of Formal Languages, Vol. I, Springer-Verlag, Berlin, 1997, 41\u2013110."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2002"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45687-2_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,18]],"date-time":"2023-02-18T02:09:38Z","timestamp":1676686178000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45687-2_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540440406","9783540456872"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/3-540-45687-2_27","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]},"assertion":[{"value":"4 October 2002","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}
