{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:53Z","timestamp":1787337473814,"version":"build-2736575974"},"reference-count":16,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>\n                    We resolve an open problem raised by Ravikumar and Ibarra [SIAM J. Comput., 18 (1989), pp. 1263--1282] on the succinctness of representations relating to the types of ambiguity of finite automata. We show that there exists a family of nondeterministic finite automata {A\n                    <jats:sub>n<\/jats:sub>\n                    } over a two-letter alphabet such that, for any positive integer n, A\n                    <jats:sub>n<\/jats:sub>\n                    is exponentially ambiguous and has n states, whereas the smallest equivalent deterministic finite automaton has 2\n                    <jats:sup>n<\/jats:sup>\n                    states, and any smallest equivalent polynomially ambiguous finite automaton has 2\n                    <jats:sup>n<\/jats:sup>\n                    -1 states.\n                  <\/jats:p>","DOI":"10.1137\/s0097539793252092","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"1073-1082","source":"Crossref","is-referenced-by-count":56,"title":["Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata"],"prefix":"10.1137","volume":"27","author":[{"given":"Hing","family":"Leung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-011-4122-2"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"F. Harary,\n                      Graph Theory\n                      , Addison\u2010Wesley, Reading, MA, 1969.","DOI":"10.21236\/AD0705364"},{"key":"R3","unstructured":"J. Hopcroft and J. Ullman,\n                      Introduction to Automata Theory, Languages and Computation\n                      , Addison\u2010Wesley, Reading, MA, 1979."},{"key":"R4","unstructured":"John Hopcroft, Jeffrey Ullman, Wprowadzenie do teorii automat\u00f3w, j\u0119zyk\u00f3w i oblicze\u0144, Wydawnictwo Naukowe PWN, Warsaw, 1994, 480\u20130, Translated from the 1979 English original by Beata Konikowska99a:68001"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"O. Ibarra and B. Ravikumar,\n                      On sparseness, ambiguity and other decision problems for acceptors and transducers\n                      , in Proc. 3rd Annual Symposium on Theoretical Aspects of Computer Science, Orsay, France, Lecture Notes in Computer Science 210, 1986, pp. 171\u2013179.","DOI":"10.1007\/3-540-16078-7_74"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Oscar Ibarra, B. Ravikumar, On sparseness, ambiguity and other decision problems for acceptors and transducers, Lecture Notes in Comput. Sci., Vol. 210, Springer, Berlin, 1986, 171\u2013179827734","DOI":"10.1007\/3-540-16078-7_74"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"A. Meyer and M. Fischer,\n                      Economy of description by automata, grammars, and formal systems\n                      , in Proc. 12th Symposium on Switching and Automata Theory, 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"A. Meyer and M. Fischer,\n                      Economy of description by automata, grammars, and formal systems\n                      , in Proc. 12th Symposium on Switching and Automata Theory, 1971, pp. 188\u2013191.","DOI":"10.1109\/SWAT.1971.11"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1971.223108"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"E. Schmidt,\n                      Succinctness of Descriptions of Context\u2010Free, Regular, and Finite Languages\n                      , Ph.D. Thesis, Cornell University, Ithaca, NY, 1978.","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"E. Schmidt,\n                      Succinctness of Descriptions of Context\u2010Free, Regular, and Finite Languages\n                      , Ph.D. Thesis, Cornell University, Ithaca, NY, 1978.","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1137\/0214044"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0214044"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539793252092","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:12:06Z","timestamp":1787335926000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539793252092"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539793252092"],"URL":"https:\/\/doi.org\/10.1137\/s0097539793252092","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}