{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:58:24Z","timestamp":1725551904854},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540311980"},{"type":"electronic","value":"9783540322177"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11611257_36","type":"book-chapter","created":{"date-parts":[[2006,1,5]],"date-time":"2006-01-05T16:37:18Z","timestamp":1136479038000},"page":"379-388","source":"Crossref","is-referenced-by-count":1,"title":["On Separating Constant from Polynomial Ambiguity of Finite Automata"],"prefix":"10.1007","author":[{"given":"Joachim","family":"Kupke","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","volume-title":"Introduction to Automata and Language Theory","author":"J. Hopcroft","year":"2000","unstructured":"Hopcroft, J., Motwani, R., Ullman, J.: Introduction to Automata and Language Theory. Addison-Wesley, Reading (2000)"},{"key":"36_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03442-2","volume-title":"Communication Complexity and Parallel Computing","author":"J. Hromkovi\u010d","year":"1997","unstructured":"Hromkovi\u010d, J.: Communication Complexity and Parallel Computing. Springer, Heidelberg (1997)"},{"key":"36_CR3","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. Hromkovi \u010d","year":"2000","unstructured":"Hromkovi \u010d, J., Karhum\u00e4ki, J., Klauck, H., Seibert, S., Schnitger, G.: Measures on 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)"},{"key":"36_CR4","unstructured":"Kupke, J.: Limiting the Ambiguity of Non-Deterministic Finite Automata. Diploma Thesis, RWTH Aachen (2002), Available online at: \n                    \n                      http:\/\/www-i1.informatik.rwth-aachen.de\/~joachimk\/ltaondfa.ps"},{"key":"36_CR5","unstructured":"Kupke, J.: On Separating Constant from Polynomial Ambiguity of Finite Automata, \n                    \n                      http:\/\/www.ite.ethz.ch\/people\/jkupke\/publications\/oscfpaofa.ps"},{"key":"36_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-540-31856-9_33","volume-title":"STACS 2005","author":"G. Gramlich","year":"2005","unstructured":"Gramlich, G., Schnitger, G.: Minimizing NFAs and Regular Expressions. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol.\u00a03404, pp. 399\u2013411. Springer, Heidelberg (2005)"},{"key":"36_CR7","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.1137\/S0097539793252092","volume":"27","author":"H. Leung","year":"1998","unstructured":"Leung, H.: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata. SIAM J.\u00a0Comp.\u00a027, 1073\u20131082 (1998)","journal-title":"SIAM J.\u00a0Comp."},{"key":"36_CR8","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F. Moore","year":"1971","unstructured":"Moore, F.: On the Bounds for State-Set Size in the Proofs of Equivalence between Deterministic, Nondeterministic, and Two-Way Finite Automata. IEEE Trans.\u00a0Comput.\u00a020, 1211\u20131214 (1971)","journal-title":"IEEE Trans.\u00a0Comput."},{"key":"36_CR9","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation. SIAM J.\u00a0Comp.\u00a018, 1263\u20131282 (1989)","journal-title":"SIAM J.\u00a0Comp."},{"issue":"2","key":"36_CR10","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M. Sipser","year":"1980","unstructured":"Sipser, M.: Lower Bounds on the Size of Sweeping Automata. J.\u00a0Comp.\u00a0and Sys.\u00a0Sci.\u00a021(2), 195\u2013202 (1980)","journal-title":"J.\u00a0Comp.\u00a0and Sys.\u00a0Sci."},{"key":"36_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"620","DOI":"10.1007\/BFb0016289","volume-title":"Mathematical Foundations of Computer Science 1986","author":"A. Weber","year":"1986","unstructured":"Weber, A., Seidl, H.: On the Ambiguity of Finite Automata. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol.\u00a0233, pp. 620\u2013629. Springer, Heidelberg (1986)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2006: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11611257_36.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:09:34Z","timestamp":1619507374000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11611257_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540311980","9783540322177"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/11611257_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}