{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:08:27Z","timestamp":1725548907351},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540249986"},{"type":"electronic","value":"9783540318569"}],"license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-31856-9_33","type":"book-chapter","created":{"date-parts":[[2010,3,2]],"date-time":"2010-03-02T18:06:19Z","timestamp":1267553179000},"page":"399-411","source":"Crossref","is-referenced-by-count":14,"title":["Minimizing NFA\u2019s and Regular Expressions"],"prefix":"10.1007","author":[{"given":"Gregor","family":"Gramlich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Schnitger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/3-540-45007-6_15","volume-title":"Developments in Language Theory","author":"J.-M. Champarnaud","year":"2003","unstructured":"Champarnaud, J.-M., Coulon, F.: NFA Reduction Algorithms by Means of Regular Inequalities. In: \u00c9sik, Z., F\u00fcl\u00f6p, Z. (eds.) DLT 2003. LNCS, vol.\u00a02710, pp. 194\u2013205. Springer, Heidelberg (2003)"},{"key":"33_CR2","unstructured":"Domaratzki, M., Kisman, D., Shallit, J.: On the Number of Distinct Languages Accepted by Finite Automata with n States. Journal of Automata, Languages and Combinatorics\u00a07(4) (2002)"},{"key":"33_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/978-3-540-45138-9_40","volume-title":"Mathematical Foundations of Computer Science 2003","author":"G. Gramlich","year":"2003","unstructured":"Gramlich, G.: Probabilistic and Nondeterministic Unary Automata. In: Rovan, B., Vojt\u00e1\u0161, P. (eds.) MFCS 2003. LNCS, vol.\u00a02747, pp. 460\u2013469. Springer, Heidelberg (2003)"},{"key":"33_CR4","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":"33_CR5","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. Informat. & Computation\u00a0186, 140\u2013162 (2003)","journal-title":"Informat. & Computation"},{"key":"33_CR6","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 NFA\u2019s over a unary alphabet. Int. J. Found. of Comp. Sci.\u00a02, 163\u2013182 (1991)","journal-title":"Int. J. Found. of Comp. Sci."},{"issue":"1","key":"33_CR7","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(1), 1117\u20131141 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"33_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Valiant, L.G.: Cryptographic Limitations on Learning Boolean Formulae and Finite Automata. Journal of the ACM\u00a041(1), 67\u201395 (1994)","journal-title":"Journal of the ACM"},{"key":"33_CR9","unstructured":"Matz, O., Potthoff, A.: Computing small nondeterministic finite automata. In: Proc. of the Workshop on Tools and Algorithms for the Construction and Analysis of Systems, Dpt. of CS., Univ. of Aarhus, pp. 74\u201388 (1995)"},{"key":"33_CR10","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Stockmeyer, L.J.: The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space. In: Proc. 13th Ann. IEEE Symp. on Switching and Automata Theory, pp. 125\u2013129 (1972)","DOI":"10.1109\/SWAT.1972.29"},{"issue":"2","key":"33_CR11","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1145\/972639.972643","volume":"51","author":"M. Naor","year":"2004","unstructured":"Naor, M., Reingold, O.: Number-Theoretic constructions of efficient pseudo-random functions. Journal of the ACM\u00a051(2), 231\u2013262 (2004)","journal-title":"Journal of the ACM"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L. Pitt","year":"1993","unstructured":"Pitt, L., Warmuth, M.K.: The Minimum Consistent DFA Problem Cannot be Approximated within any Polynomial. Journ. of the ACM\u00a040, 95\u2013142 (1993)","journal-title":"Journ. of the ACM"},{"issue":"3","key":"33_CR13","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L., Warmuth, M.K.: Prediction-Preserving Reducibility. Journal of Computer and System Science\u00a041(3), 430\u2013467 (1990)","journal-title":"Journal of Computer and System Science"},{"key":"33_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1006\/jcss.1997.1494","volume":"55","author":"A.A. Razborov","year":"1997","unstructured":"Razborov, A.A., Rudich, S.: Natural Proofs. Journal of Computer and Systems Sciences\u00a055, 24\u201335 (1997)","journal-title":"Journal of Computer and Systems Sciences"},{"key":"33_CR15","doi-asserted-by":"crossref","unstructured":"Stockmeyer, L., Meyer, A.: Word Problems Requiring Exponential Time. In: Proc. of the 5th Annual ACM Symposium on Theory of Computing, pp. 1\u20139 (1973)","DOI":"10.1145\/800125.804029"}],"container-title":["Lecture Notes in Computer Science","STACS 2005"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-31856-9_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T17:30:36Z","timestamp":1558287036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-31856-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540249986","9783540318569"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-31856-9_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}