{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T13:40:10Z","timestamp":1742391610135},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642151545"},{"type":"electronic","value":"9783642151552"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15155-2_49","type":"book-chapter","created":{"date-parts":[[2010,8,13]],"date-time":"2010-08-13T20:17:45Z","timestamp":1281730665000},"page":"556-567","source":"Crossref","is-referenced-by-count":11,"title":["Unambiguous Finite Automata over a Unary Alphabet"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"49_CR1","volume-title":"Algorithmic Number Theory","author":"E. Bach","year":"1996","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory. MIT Press, Cambridge (1996)"},{"key":"49_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/978-3-540-70583-3_3","volume-title":"Automata, Languages and Programming","author":"H. Bj\u00f6rklund","year":"2008","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol.\u00a05126, pp. 27\u201338. Springer, Heidelberg (2008)"},{"issue":"1-3","key":"49_CR3","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M. Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoretical Computer Science\u00a047, 149\u2013158 (1986); Errata: vol.\u00a0302(1-3), pp. 497\u2013498 (2003)","journal-title":"Theoretical Computer Science"},{"issue":"8","key":"49_CR4","doi-asserted-by":"publisher","first-page":"1173","DOI":"10.1016\/j.ic.2007.01.008","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Complementing two-way finite automata. Information and Computation\u00a0205(8), 1173\u20131187 (2007)","journal-title":"Information and Computation"},{"key":"49_CR5","doi-asserted-by":"publisher","first-page":"1087","DOI":"10.1142\/S0129054103002199","volume":"14","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Intl. J. of Foundations of Computer Science\u00a014, 1087\u20131102 (2003)","journal-title":"Intl. J. of Foundations of Computer Science"},{"issue":"2","key":"49_CR6","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J. Hromkovi\u010d","year":"2002","unstructured":"Hromkovi\u010d, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Information and Computation\u00a0172(2), 202\u2013217 (2002)","journal-title":"Information and Computation"},{"key":"49_CR7","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-31.4.445","volume":"31","author":"A.W. Ingleton","year":"1956","unstructured":"Ingleton, A.W.: The rank of circulant matrices. Journal of the London Mathematical Society\u00a031, 445\u2013460 (1956)","journal-title":"Journal of the London Mathematical Society"},{"issue":"2","key":"49_CR8","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. International Journal of Foundations of Computer Science\u00a02(2), 163\u2013182 (1991)","journal-title":"International Journal of Foundations of Computer Science"},{"issue":"5","key":"49_CR9","first-page":"92","volume":"3","author":"E. Landau","year":"1903","unstructured":"Landau, E.: \u00dcber die Maximalordnung der Permutationen gegebenen Grades (On the maximal order of permutations of a given degree). Archiv der Mathematik und Physik\u00a03(5), 92\u2013103 (1903)","journal-title":"Archiv der Mathematik und Physik"},{"issue":"4","key":"49_CR10","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 Journal on Computing\u00a027(4), 1073\u20131082 (1998)","journal-title":"SIAM Journal on Computing"},{"issue":"5","key":"49_CR11","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1142\/S0129054105003418","volume":"16","author":"H. Leung","year":"2005","unstructured":"Leung, H.: Descriptional complexity of NFA of different ambiguity. International Journal of Foundations of Computer Science\u00a016(5), 975\u2013984 (2005)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"49_CR12","first-page":"337","volume":"2","author":"Y. Lyubich","year":"1964","unstructured":"Lyubich, Y.: Bounds for the optimal determinization of nondeterministic autonomic automata. Sibirskii Matematicheskii Zhurnal\u00a02, 337\u2013355 (1964) (in Russian)","journal-title":"Sibirskii Matematicheskii Zhurnal"},{"key":"49_CR13","first-page":"1373","volume":"11","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Soviet Mathematics Doklady\u00a011, 1373\u20131375 (1970)","journal-title":"Soviet Mathematics Doklady"},{"issue":"2","key":"49_CR14","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.tcs.2004.04.015","volume":"330","author":"F. Mera","year":"2005","unstructured":"Mera, F., Pighizzini, G.: Complementing unary nondeterministic automata. Theoretical Computer Science\u00a0330(2), 349\u2013360 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"6","key":"49_CR15","doi-asserted-by":"publisher","first-page":"1976","DOI":"10.1137\/S009753979935431X","volume":"30","author":"C. Mereghetti","year":"2001","unstructured":"Mereghetti, C., Pighizzini, G.: Optimal simulations between unary automata. SIAM Journal on Computing\u00a030(6), 1976\u20131992 (2001)","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"49_CR16","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/2322839","volume":"94","author":"W. Miller","year":"1987","unstructured":"Miller, W.: The maximum order of an element of a finite symmetric group. American Mathematical Monthly\u00a094(6), 497\u2013506 (1987)","journal-title":"American Mathematical Monthly"},{"issue":"1","key":"49_CR17","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1142\/S012905410200100X","volume":"13","author":"G. Pighizzini","year":"2002","unstructured":"Pighizzini, G., Shallit, J.: Unary language operations, state complexity and Jacobsthal\u2019s function. Intl. J. of Foundations of Computer Sci.\u00a013(1), 145\u2013159 (2002)","journal-title":"Intl. J. of Foundations of Computer Sci."},{"key":"49_CR18","first-page":"181","volume":"11","author":"S. Ramanujan","year":"1919","unstructured":"Ramanujan, S.: A proof of Bertrand\u2019s postulate. Journal of the Indian Mathematical Society\u00a011, 181\u2013182 (1919)","journal-title":"Journal of the Indian Mathematical Society"},{"key":"49_CR19","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of Description of Context-Free, Regular and Unambiguous Languages, Ph. D. thesis, Cornell University (1978)","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"49_CR20","doi-asserted-by":"publisher","first-page":"630","DOI":"10.4169\/193009709X458609","volume":"116","author":"J. Sondow","year":"2009","unstructured":"Sondow, J.: Ramanujan primes and Bertrand\u2019s postulate. American Mathematical Monthly\u00a0116, 630\u2013635 (2009)","journal-title":"American Mathematical Monthly"},{"key":"49_CR21","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 Journal on Computing\u00a014, 598\u2013611 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"49_CR22","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S. Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexity of some basic operations on regular languages. Theoretical Computer Science\u00a0125, 315\u2013328 (1994)","journal-title":"Theoretical Computer Science"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2010"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15155-2_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:47Z","timestamp":1606186907000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15155-2_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642151545","9783642151552"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15155-2_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}