{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:08:53Z","timestamp":1725664133619},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540575689"},{"type":"electronic","value":"9783540482338"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-57568-5_252","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T13:09:45Z","timestamp":1330261785000},"page":"221-229","source":"Crossref","is-referenced-by-count":3,"title":["Separating exponentially ambiguous NFA from polynomially ambiguous NFA"],"prefix":"10.1007","author":[{"given":"Hing","family":"Leung","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph theory","author":"F. Harary","year":"1969","unstructured":"F. Harary, Graph theory, Addison-Wesley, Reading, MA, 1969."},{"key":"24_CR2","volume-title":"Introduction to automata theory, languages and computation","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman, Introduction to automata theory, languages and computation, Addison-Wesley, Reading, MA, 1979."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"O. Ibarra and B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers, Proc. 3rd Annual Symposium on Theoretical Aspects of Computer Science, 1986, pp. 171\u2013179.","DOI":"10.1007\/3-540-16078-7_74"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"A. Meyer and M. Fischer, Economy of description by automata, grammars, and formal systems, Proc. 12th Symposium on Switching and Automata Theory, 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"24_CR5","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"F. Moore","year":"1971","unstructured":"F. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata, IEEE Trans. Comput., 20 (1971), pp. 1211\u20131214.","journal-title":"IEEE Trans. Comput."},{"key":"24_CR6","unstructured":"C. Reutenauer, Propri\u00e9t\u00e9s arithm\u00e9tiques et topologiques de s\u00e9ries rationnelles en variables non commutatives, Th\u00e8se troisi\u00e8me cycle, Universit\u00e9 Paris VI, 1977."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"B. Ravikumar and O. Ibarra, Relating the type of ambiguity of finite automata to the succinctness of their representation, SIAM J. Comput., 18 (1989), pp. 1263\u20131282.","journal-title":"SIAM J. Comput."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"E. Schmidt, Succinctness of descriptions of context-free, regular, and finite languages, Ph.D. Thesis, Cornell University, 1978.","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"24_CR9","doi-asserted-by":"crossref","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"R. Stearns","year":"1985","unstructured":"R. Stearns and H. Hunt, On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata, SIAM J. Comput., 14 (1985), pp. 598\u2013611.","journal-title":"SIAM J. Comput."},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"A. Weber","year":"1991","unstructured":"A. Weber and H. Seidl, On the degree of ambiguity of finite automata, Theoret. Comput. Sci., 88 (1991), pp. 325\u2013349.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-57568-5_252.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:13:12Z","timestamp":1605647592000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-57568-5_252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540575689","9783540482338"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-57568-5_252","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}