{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:12:14Z","timestamp":1725516734498},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705826"},{"type":"electronic","value":"9783540705833"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70583-3_3","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"27-38","source":"Crossref","is-referenced-by-count":7,"title":["The Tractability Frontier for NFA Minimization"],"prefix":"10.1007","author":[{"given":"Henrik","family":"Bj\u00f6rklund","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Abdulla, P., Deneux, J., Kaati, L., Nilsson, M.: Minimization of non-deterministic automata with large alphabets. In: CIAA, pp. 31\u201342 (2006)","DOI":"10.1007\/11605157_3"},{"issue":"2","key":"3_CR2","first-page":"193","volume":"8","author":"J. Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. Univ. Comp. Science\u00a08(2), 193\u2013234 (2002)","journal-title":"J. Univ. Comp. Science"},{"issue":"6","key":"3_CR3","first-page":"908","volume":"73","author":"G. Gramlich","year":"2007","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFAs and regular expressions. JCSS\u00a073(6), 908\u2013923 (2007)","journal-title":"JCSS"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/11779148_33","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2006","unstructured":"Gruber, H., Holzer, M.: Finding lower bounds for nondeterministic state complexity is hard. In: H. Ibarra, O., Dang, Z. (eds.) DLT 2006. LNCS, vol.\u00a04036, pp. 363\u2013374. Springer, Heidelberg (2006)"},{"key":"3_CR5","unstructured":"Gruber, H., Holzer, M.: Computational complexity of NFA minimization for finite and unary languages. In: LATA, pp. 261\u2013272 (2007)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-540-73208-2_21","volume-title":"Developments in Language Theory","author":"H. Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: Inapproximability of nondeterministic state and transition complexity assuming P \u2260 NP. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 205\u2013216. Springer, Heidelberg (2007)"},{"issue":"4","key":"3_CR7","first-page":"453","volume":"6","author":"M. Holzer","year":"2001","unstructured":"Holzer, M., Salomaa, K., Yu, S.: On the state complexity of k-entry deterministic finite automata. J. Automata, Languages, and Combinatorics\u00a06(4), 453\u2013466 (2001)","journal-title":"J. Automata, Languages, and Combinatorics"},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/3-540-45022-X_17","volume-title":"Automata, Languages and Programming","author":"J. Hromkovic","year":"2000","unstructured":"Hromkovic, J., Karhum\u00e4ki, J., Klauck, H., Schnitger, G., Seibert, S.: Measures of nondeterminism in finite automata. In: Welzl, E., Montanari, U., Rolim, J.D.P. (eds.) ICALP 2000. LNCS, vol.\u00a01853, pp. 199\u2013210. Springer, Heidelberg (2000)"},{"issue":"2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tcs.2007.02.063","volume":"380","author":"J. Hromkovic","year":"2007","unstructured":"Hromkovic, J., Schnitger, G.: Comparing the size of NFAs with and without epsilon-transitions. TCS\u00a0380(2), 100\u2013114 (2007)","journal-title":"TCS"},{"key":"3_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1142\/S012905419100011X","volume":"2","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal NFAs over unary alphabet. Int. J. Found. Comp. Science\u00a02, 163\u2013182 (1991)","journal-title":"Int. J. Found. Comp. Science"},{"issue":"6","key":"3_CR11","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 J. Comp.\u00a022(6), 1117\u20131141 (1993)","journal-title":"Siam J. Comp."},{"issue":"3","key":"3_CR12","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.tcs.2004.03.070","volume":"327","author":"A. Malcher","year":"2004","unstructured":"Malcher, A.: Minimizing finite automata is computationally hard. TCS\u00a0327(3), 375\u2013390 (2004)","journal-title":"TCS"},{"key":"3_CR13","first-page":"188","volume-title":"FOCS","author":"A. Meyer","year":"1971","unstructured":"Meyer, A., Fischer, M.J.: Economy of descriptions by automata, grammars, and formal systems. In: FOCS, pp. 188\u2013191. IEEE, Los Alamitos (1971)"},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"973","DOI":"10.1137\/0216062","volume":"16","author":"R. Paige","year":"1987","unstructured":"Paige, R., Tarjan, R.: Three parition refinement algorithms. Siam J. Comp.\u00a016, 973\u2013989 (1987)","journal-title":"Siam J. Comp."},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-540-73208-2_6","volume-title":"Developments in Language Theory","author":"K. Salomaa","year":"2007","unstructured":"Salomaa, K.: Descriptional complexity of nondeterministic finite automata. In: Harju, T., Karhum\u00e4ki, J., Lepist\u00f6, A. (eds.) DLT 2007. LNCS, vol.\u00a04588, pp. 31\u201335. Springer, Heidelberg (2007)"},{"key":"3_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G. Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFAs without epsilon-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"issue":"3","key":"3_CR17","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R.E. Stearns","year":"1985","unstructured":"Stearns, R.E., Hunt III., H.B.: On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. Siam J. Comp.\u00a014(3), 598\u2013611 (1985)","journal-title":"Siam J. Comp."},{"key":"3_CR18","first-page":"1","volume-title":"STOC","author":"L. Stockmeyer","year":"1973","unstructured":"Stockmeyer, L., Meyer, A.: Word problems requiring exponential time: Preliminary report. In: STOC, pp. 1\u20139. ACM, New York (1973)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70583-3_3.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T04:23:34Z","timestamp":1620015814000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70583-3_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540705826","9783540705833"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70583-3_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}