{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T10:51:24Z","timestamp":1794480684506,"version":"4.9.1"},"publisher-location":"Cham","reference-count":29,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319097039","type":"print"},{"value":"9783319097046","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-09704-6_29","type":"book-chapter","created":{"date-parts":[[2014,7,11]],"date-time":"2014-07-11T05:43:21Z","timestamp":1405057401000},"page":"330-341","source":"Crossref","is-referenced-by-count":1,"title":["State Complexity of Unary Language Operations for NFAs with Limited Nondeterminism"],"prefix":"10.1007","author":[{"given":"Alexandros","family":"Palioudakis","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Selim G.","family":"Akl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"1","key":"29_CR1","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.jnt.2006.05.020","volume":"123","author":"I.M. Aliev","year":"2007","unstructured":"Aliev, I.M., Gruber, P.M.: An optimal lower bound for the Frobenius problem. Journal of Number Theory\u00a0123(1), 71\u201379 (2007)","journal-title":"Journal of Number Theory"},{"key":"29_CR2","unstructured":"Bach, E., Shallit, J.: Algorithmic Number Theory: Efficient Algorithms, vol.\u00a01. MIT Press (1996)"},{"issue":"1","key":"29_CR3","first-page":"1","volume":"96","author":"M. Beck","year":"2002","unstructured":"Beck, M., Diaz, R., Robins, S.: The Frobenius problem, rational polytopes, and fourier\u2013dedekind sums. Journal of Number Theory\u00a096(1), 1\u201321 (2002)","journal-title":"Journal of Number Theory"},{"issue":"3","key":"29_CR4","doi-asserted-by":"publisher","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. Theor. Comput. Sci.\u00a047(3), 149\u2013158 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"29_CR5","unstructured":"Gao, Y., Moreira, N., Reis, R., Sheng, Y.: A review of state complexity of individual operations. Technical report, Universidade do Porto, Technical Report Series DCC-2011-08, Version 1.1 (2012), \n                  \n                    http:\/\/www.dcc.fc.up.pt\/Pubs"},{"key":"29_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1007\/978-3-642-22256-6_14","volume-title":"Implementation and Application of Automata","author":"P. Gawrychowski","year":"2011","unstructured":"Gawrychowski, P.: Chrobak normal form revisited, with applications. In: Bouchou-Markhoff, B., Caron, P., Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2011. LNCS, vol.\u00a06807, pp. 142\u2013153. Springer, Heidelberg (2011)"},{"issue":"2","key":"29_CR7","first-page":"193","volume":"8","author":"J. Goldstine","year":"2002","unstructured":"Goldstine, J., Kappes, M., Kintala, C.M.R., Leung, H., Malcher, A., Wotschke, D.: Descriptional complexity of machines with limited resources. J. UCS\u00a08(2), 193\u2013234 (2002)","journal-title":"J. UCS"},{"issue":"2","key":"29_CR8","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/0890-5401(90)90053-K","volume":"86","author":"J. Goldstine","year":"1990","unstructured":"Goldstine, J., Kintala, C.M.R., Wotschke, D.: On measuring nondeterminism in regular languages. Inf. Comput.\u00a086(2), 179\u2013194 (1990)","journal-title":"Inf. Comput."},{"issue":"6","key":"29_CR9","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. Int. J. Found. Comput. Sci.\u00a014(6), 1087\u20131102 (2003)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"29_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1007\/3-540-45005-X_14","volume-title":"Developments in Language Theory","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: Unary language operations and their nondeterministic state complexity. In: Ito, M., Toyama, M. (eds.) DLT 2002. LNCS, vol.\u00a02450, pp. 162\u2013172. Springer, Heidelberg (2003)"},{"issue":"4","key":"29_CR11","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1142\/S0129054109006747","volume":"20","author":"M. Holzer","year":"2009","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic finite automata - recent results on the descriptional and computational complexity. Int. J. Found. Comput. Sci.\u00a020(4), 563\u2013580 (2009)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"3","key":"29_CR12","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M. Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata - a survey. Inf. Comput.\u00a0209(3), 456\u2013470 (2011)","journal-title":"Inf. Comput."},{"key":"29_CR13","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., Schnitger, G., Seibert, S.: Measures of 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)"},{"issue":"2","key":"29_CR14","doi-asserted-by":"publisher","first-page":"202","DOI":"10.1006\/inco.2001.3069","volume":"172","author":"J. Hromkovic","year":"2002","unstructured":"Hromkovic, J., Seibert, S., Karhum\u00e4ki, J., Klauck, H., Schnitger, G.: Communication complexity method for measuring nondeterminism in finite automata. Inf. Comput.\u00a0172(2), 202\u2013217 (2002)","journal-title":"Inf. Comput."},{"key":"29_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"152","DOI":"10.1007\/3-540-54967-6_67","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., McDowell, E., Ravikumar, B.: The structure and complexity of minimal nfa\u2019s over a unary alphabet. In: Biswas, S., Nori, K.V. (eds.) FSTTCS 1991. LNCS, vol.\u00a0560, pp. 152\u2013171. Springer, Heidelberg (1991)"},{"key":"29_CR16","unstructured":"Kutrib, M., Pighizzini, G.: Recent trends in descriptional complexity of formal languages. Bulletin of EATCS\u00a03(111) (2013)"},{"issue":"4","key":"29_CR17","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. Comput.\u00a027(4), 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"29_CR18","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. Int. J. Found. Comput. Sci.\u00a016(5), 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"29_CR19","first-page":"1266","volume":"194","author":"A.N. Maslov","year":"1970","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Doklady Akademii Nauk SSSR\u00a0194, 1266\u20131268 (1970)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"29_CR20","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: SWAT (FOCS), pp. 188\u2013191. IEEE Computer Society (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"29_CR21","doi-asserted-by":"crossref","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers\u00a0C-20(10), 1211\u20131214 (1971)","DOI":"10.1109\/T-C.1971.223108"},{"key":"29_CR22","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.ic.2012.01.003","volume":"212","author":"A. Okhotin","year":"2012","unstructured":"Okhotin, A.: Unambiguous finite automata over a unary alphabet. Inf. Comput.\u00a0212, 15\u201336 (2012)","journal-title":"Inf. Comput."},{"key":"29_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-642-31623-4_20","volume-title":"Descriptional Complexity of Formal Systems","author":"A. Palioudakis","year":"2012","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity and limited nondeterminism. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol.\u00a07386, pp. 252\u2013265. Springer, Heidelberg (2012)"},{"key":"29_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-642-39310-5_21","volume-title":"Descriptional Complexity of Formal Systems","author":"A. Palioudakis","year":"2013","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Comparisons between measures of nondeterminism on finite automata. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol.\u00a08031, pp. 217\u2013228. Springer, Heidelberg (2013)"},{"key":"29_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/978-3-319-04298-5_39","volume-title":"SOFSEM 2014: Theory and Practice of Computer Science","author":"A. Palioudakis","year":"2014","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Unary nfas with limited nondeterminism. In: Geffert, V., Preneel, B., Rovan, B., \u0160tuller, J., Tjoa, A.M. (eds.) SOFSEM 2014. LNCS, vol.\u00a08327, pp. 443\u2013454. Springer, Heidelberg (2014)"},{"issue":"1","key":"29_CR26","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. Int. J. Found. Comput. Sci.\u00a013(1), 145\u2013159 (2002)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"29_CR27","doi-asserted-by":"crossref","unstructured":"Shallit, J.O.: A Second Course in Formal Languages and Automata Theory. Cambridge University Press (2008)","DOI":"10.1017\/CBO9780511808876"},{"issue":"2","key":"29_CR28","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 complexities of some basic operations on regular languages. Theoret. Comput. Sci.\u00a0125(2), 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."},{"key":"29_CR29","doi-asserted-by":"crossref","unstructured":"Sheng, Y.: Regular Languages. In: Handbook of Formal Languages, vol.\u00a01, pp. 41\u2013110. Springer (1998)","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-09704-6_29","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T05:01:48Z","timestamp":1558933308000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-09704-6_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319097039","9783319097046"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-09704-6_29","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-09704-6","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}