{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T12:00:16Z","timestamp":1725796816459},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319088457"},{"type":"electronic","value":"9783319088464"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-08846-4_18","type":"book-chapter","created":{"date-parts":[[2014,7,4]],"date-time":"2014-07-04T07:56:43Z","timestamp":1404460603000},"page":"238-251","source":"Crossref","is-referenced-by-count":1,"title":["Left is Better than Right for Reducing Nondeterminism of NFAs"],"prefix":"10.1007","author":[{"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-642-02979-0_10","volume-title":"Implementation and Application of Automata","author":"A. Almeida","year":"2009","unstructured":"Almeida, A., Almeida, M., Alves, J., Moreira, N., Reis, R.: FAdo and gUItar: Tools for automata manipulation and visualization. In: Maneth, S. (ed.) CIAA 2009. LNCS, vol.\u00a05642, pp. 65\u201374. Springer, Heidelberg (2009)"},{"issue":"2","key":"18_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. Theoretical Computer Science\u00a0155(2), 291\u2013319 (1996)","journal-title":"Theoretical Computer Science"},{"key":"18_CR3","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. Theoretical Computer Science\u00a0120, 197\u2013213 (1993)","journal-title":"Theoretical Computer Science"},{"issue":"1-2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0304-3975(97)00296-X","volume":"233","author":"P. Caron","year":"2000","unstructured":"Caron, P., Ziadi, D.: Characterization of Glushkov automata. Theoretical Computer Science\u00a0233(1-2), 75\u201390 (2000)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2004.02.048","volume":"327","author":"J.-M. Champarnaud","year":"2004","unstructured":"Champarnaud, J.-M., Coulon, F.: NFA reduction algorithms by means of regular inequalities. Theoretical Computer Science\u00a0327(3), 241\u2013253 (2004)","journal-title":"Theoretical Computer Science"},{"key":"18_CR6","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 Mathematical Surveys\u00a016, 1\u201353 (1961)","journal-title":"Russian Mathematical Surveys"},{"key":"18_CR7","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (1979)","edition":"2"},{"issue":"2","key":"18_CR8","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Information and Computation\u00a0172(2), 202\u2013217 (2002)","journal-title":"Information and Computation"},{"key":"18_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1007\/978-3-540-27812-2_11","volume-title":"Theory Is Forever","author":"L. Ilie","year":"2004","unstructured":"Ilie, L., Navarro, G., Yu, S.: On NFA reductions. In: Karhum\u00e4ki, J., Maurer, H., P\u0103un, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol.\u00a03113, pp. 112\u2013124. Springer, Heidelberg (2004)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/11496656_27","volume-title":"Combinatorial Pattern Matching","author":"L. Ilie","year":"2005","unstructured":"Ilie, L., Solis-Oba, R., Yu, S.: Reducing the size of nFAs by using equivalences and preorders. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 310\u2013321. Springer, Heidelberg (2005)"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/3-540-45687-2_27","volume-title":"Mathematical Foundations of Computer Science 2002","author":"L. Ilie","year":"2002","unstructured":"Ilie, L., Yu, S.: Algorithms for computing small NFAs. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 328\u2013340. Springer, Heidelberg (2002)"},{"key":"18_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. Information and Computation\u00a0186, 140\u2013162 (2003)","journal-title":"Information and Computation"},{"issue":"1-3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1016\/S0304-3975(03)00311-6","volume":"306","author":"L. Ilie","year":"2003","unstructured":"Ilie, L., Yu, S.: Reducing NFAs by invariant equivalences. Theoretical Computer Science\u00a0306(1-3), 373\u2013390 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"18_CR14","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM Journal on Computing\u00a022(6), 1117\u20131141 (1993)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/978-3-540-30500-2_2","volume-title":"Implementation and Application of Automata","author":"J. Lee","year":"2005","unstructured":"Lee, J., Shallit, J.: Enumerating regular expressions and their languages. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 2\u201322. Springer, Heidelberg (2005)"},{"issue":"2","key":"18_CR16","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(94)90033-7","volume":"49","author":"H.G. Mairson","year":"1994","unstructured":"Mairson, H.G.: Generating words in a context-free language uniformly at random. Information Processing Letters\u00a049(2), 95\u201399 (1994)","journal-title":"Information Processing Letters"},{"issue":"1","key":"18_CR17","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. IRE Transactions on Electronic Computers\u00a09(1), 39\u201347 (1960)","journal-title":"IRE Transactions on Electronic Computers"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Navarro, G., Raffinot, M.: Compact DFA representation for fast regular expression search. In: Proceedings of the 5th International Workshop on Algorithm Engineering, pp. 1\u201312 (2001)","DOI":"10.1007\/3-540-44688-5_1"},{"key":"18_CR19","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316135228","volume-title":"Flexible Pattern Matching in Strings: Practical On-line Search Algorithms for Texts and Biological Sequences","author":"G. Navarro","year":"2002","unstructured":"Navarro, G., Raffinot, M.: Flexible Pattern Matching in Strings: Practical On-line Search Algorithms for Texts and Biological Sequences. Cambridge University Press, New York (2002)"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-39310-5_21","volume-title":"Descriptional Complexity of Formal Systems","author":"A. Palioudakis","year":"2013","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Comparisons between measures of nondeterminism on finite automata. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 217\u2013228. Springer, Heidelberg (2013)"},{"issue":"6","key":"18_CR21","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. Communications of the ACM\u00a011(6), 419\u2013422 (1968)","journal-title":"Communications of the ACM"},{"key":"18_CR22","unstructured":"Wood, D.: Theory of Computation. Harper & Row (1987)"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-08846-4_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T02:28:48Z","timestamp":1558924128000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-08846-4_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319088457","9783319088464"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-08846-4_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}