{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T10:06:00Z","timestamp":1695117960360},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2010,12,8]],"date-time":"2010-12-08T00:00:00Z","timestamp":1291766400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2012,7]]},"DOI":"10.1007\/s00453-010-9479-9","type":"journal-article","created":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T15:21:44Z","timestamp":1291735304000},"page":"571-587","source":"Crossref","is-referenced-by-count":6,"title":["Pairs of Complementary Unary Languages with\u00a0\u201cBalanced\u201d Nondeterministic Automata"],"prefix":"10.1007","volume":"63","author":[{"given":"Viliam","family":"Geffert","sequence":"first","affiliation":[]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,8]]},"reference":[{"key":"9479_CR1","author":"M. Anselmo","year":"2010","unstructured":"Anselmo, M., Madonia, M.: Some results on the structure of unary unambiguous automata. Adv. Appl. Math. (2010). doi: 10.1016\/j.aam.2010.05.003","journal-title":"Adv. Appl. Math."},{"key":"9479_CR2","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. Theor. Comput. Sci. 47, 149\u2013158 (1986). Corrigendum: ibid. 302, 497\u2013498 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9479_CR3","series-title":"LNCS","first-page":"117","volume-title":"Proceedings of Symposium on Theoretical Aspects of Computer Science 1997","author":"P. \u010euri\u0161","year":"1997","unstructured":"\u010euri\u0161, P., Hromkovi\u010d, J., Rolim, J., Schnitger, G.: Las Vegas versus determinism for one-way communication complexity, finite automata, and polynomial-time computations. In: Proceedings of Symposium on Theoretical Aspects of Computer Science 1997. LNCS, vol. 1200, pp. 117\u2013128. Springer, Berlin (1997)"},{"key":"9479_CR4","doi-asserted-by":"crossref","first-page":"1652","DOI":"10.1016\/j.ic.2007.07.001","volume":"205","author":"V. Geffert","year":"2007","unstructured":"Geffert, V.: Magic numbers in the state hierarchy of finite automata. Inf. Comput. 205, 1652\u20131670 (2007)","journal-title":"Inf. Comput."},{"key":"9479_CR5","first-page":"407","volume":"64","author":"J. Grantham","year":"1995","unstructured":"Grantham, J.: The largest prime dividing the maximal order of an element of S n . Math. Comput. 64, 407\u2013410 (1995)","journal-title":"Math. Comput."},{"key":"9479_CR6","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1006\/inco.2001.3040","volume":"169","author":"J. Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Schnitger, G.: On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inf. Comput. 169, 284\u2013296 (2001)","journal-title":"Inf. Comput."},{"key":"9479_CR7","doi-asserted-by":"crossref","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. Int. J. Found. Comput. Sci. 2, 163\u2013182 (1991)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"9479_CR8","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/978-3-642-00982-2_39","volume-title":"Proceedings of Language and Automata Theory and Applications 2009","author":"G. Jir\u00e1skov\u00e1","year":"2009","unstructured":"Jir\u00e1skov\u00e1, G., Pighizzini, G.: Converting self-verifying automata into deterministic automata. In: Proceedings of Language and Automata Theory and Applications 2009. LNCS, vol. 5457, pp. 458\u2013468. Springer, Berlin (2009)"},{"key":"9479_CR9","first-page":"92","volume":"3","author":"E. Landau","year":"1903","unstructured":"Landau, E.: \u00dcber die Maximalordnung der Permutation gegebenen Grades. Arch. Math. Phys. 3, 92\u2013103 (1903)","journal-title":"Arch. Math. Phys."},{"key":"9479_CR10","volume-title":"Handbuch der Lehre von der Verteilung der Primzahlen I","author":"E. Landau","year":"1909","unstructured":"Landau, E.: Handbuch der Lehre von der Verteilung der Primzahlen I. Teubner, Leipzig\/Berlin (1909)"},{"key":"9479_CR11","first-page":"337","volume":"V\/2","author":"Ju.I. Ljubi\u010d","year":"1964","unstructured":"Ljubi\u010d, Ju.I.: Bounds for the optimal determinization of nondeterministic autonomous automata. Sib. Mat. Zh. V\/2, 337\u2013355 (1964) (in Russian)","journal-title":"Sib. Mat. Zh."},{"key":"9479_CR12","first-page":"321","volume":"9","author":"O.B. Lupanov","year":"1963","unstructured":"Lupanov, O.B.: A comparison of two types of finite automata. Probl. Kibern. 9, 321\u2013326 (1963) (in Russian). German translation: \u00dcber den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6, 329\u2013335 (1966)","journal-title":"Probl. Kibern."},{"key":"9479_CR13","first-page":"263","volume-title":"Proceedings of 7th Princeton Conference of Information and System Sciences","author":"R. Mandl","year":"1973","unstructured":"Mandl, R.: Precise bounds associated with the subset construction of various classes of nondeterministic finite automata. In: Proceedings of 7th Princeton Conference of Information and System Sciences, pp. 263\u2013267 (1973)"},{"key":"9479_CR14","doi-asserted-by":"crossref","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. Theor. Comput. Sci. 330, 349\u2013360 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9479_CR15","doi-asserted-by":"crossref","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 J. Comput. 30, 1976\u20131992 (2001)","journal-title":"SIAM J. Comput."},{"key":"9479_CR16","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1109\/SWAT.1971.11","volume-title":"Proceedings of 12th Annual IEEE Symposium on Switching and Automata Theory","author":"A.R. Meyer","year":"1971","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proceedings of 12th Annual IEEE Symposium on Switching and Automata Theory, pp. 188\u2013191 (1971)"},{"key":"9479_CR17","doi-asserted-by":"crossref","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. Am. Math. Mon. 94, 497\u2013506 (1987)","journal-title":"Am. Math. Mon."},{"issue":"10","key":"9479_CR18","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-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. Comput. C-20(10), 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"9479_CR19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.4064\/aa-14-3-315-332","volume":"14","author":"J.-L. Nicolas","year":"1968","unstructured":"Nicolas, J.-L.: Sur l\u2019ordre maximum d\u2019un \u00e9l\u00e9ment dans le groupe S n des permutations. Acta Arith. 14, 315\u2013332 (1968)","journal-title":"Acta Arith."},{"key":"9479_CR20","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"556","DOI":"10.1007\/978-3-642-15155-2_49","volume-title":"Proceedings of Mathematical Foundations of Computer Science 2010","author":"A. Okhotin","year":"2010","unstructured":"Okhotin, A.: Unambiguous finite automata over a unary alphabet. In: Proceedings of Mathematical Foundations of Computer Science 2010. LNCS, vol. 6281, pp. 556\u2013567. Springer, Berlin (2010)"},{"key":"9479_CR21","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M. Rabin","year":"1959","unstructured":"Rabin, M., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"9479_CR22","first-page":"181","volume":"11","author":"S. Ramanujan","year":"1919","unstructured":"Ramanujan, S.: A proof of Bertrand\u2019s postulate. J. Indian Math. Soc. 11, 181\u2013182 (1919)","journal-title":"J. Indian Math. Soc."},{"key":"9479_CR23","doi-asserted-by":"crossref","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. Comput. 18, 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"key":"9479_CR24","doi-asserted-by":"crossref","first-page":"321","DOI":"10.4064\/aa-37-1-321-331","volume":"37","author":"M. Szalay","year":"1980","unstructured":"Szalay, M.: On the maximal order in S n and $S_{n}^{*}$ . Acta Arith. 37, 321\u2013331 (1980)","journal-title":"Acta Arith."},{"key":"9479_CR25","doi-asserted-by":"crossref","first-page":"1010","DOI":"10.1016\/j.ipl.2009.06.005","volume":"109","author":"A.W. To","year":"2009","unstructured":"To, A.W.: Unary finite automata vs. arithmetic progressions. Inf. Process. Lett. 109, 1010\u20131014 (2009)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9479-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-010-9479-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-010-9479-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T21:51:39Z","timestamp":1559857899000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-010-9479-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,8]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["9479"],"URL":"https:\/\/doi.org\/10.1007\/s00453-010-9479-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,8]]}}}