{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:32:12Z","timestamp":1759638732843},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319602516"},{"type":"electronic","value":"9783319602523"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-60252-3_16","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T14:59:13Z","timestamp":1496415553000},"page":"202-213","source":"Crossref","is-referenced-by-count":3,"title":["Branching Measures and Nearly Acyclic NFAs"],"prefix":"10.1007","author":[{"given":"Chris","family":"Keeler","sequence":"first","affiliation":[]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"issue":"1","key":"16_CR1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/j.jcss.2011.03.001","volume":"78","author":"H Bj\u00f6rklund","year":"2012","unstructured":"Bj\u00f6rklund, H., Martens, W.: The tractability frontier for NFA minimization. J. Comput. Syst. Sci. 78(1), 198\u2013210 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"16_CR2","doi-asserted-by":"crossref","first-page":"238","DOI":"10.1016\/j.dam.2013.08.003","volume":"163","author":"J Bubenzer","year":"2014","unstructured":"Bubenzer, J.: Cycle-aware minimization of acyclic deterministic finite-state automata. Discrete Appl. Math. 163, 238\u2013246 (2014)","journal-title":"Discrete Appl. Math."},{"key":"16_CR3","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0304-3975(88)90012-6","volume":"23","author":"T-H Chan","year":"1983","unstructured":"Chan, T.-H., Ibarra, O.: On the finite valuedness problem for sequential machines. Theoret. Comput. Sci. 23, 95\u2013101 (1983)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR4","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. Theoret. Comput. Sci. 47, 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR5","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press, Cambridge (2009)","edition":"3"},{"key":"16_CR6","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0890-5401(92)90014-7","volume":"100","author":"J Goldstine","year":"1992","unstructured":"Goldstine, J., Leung, H., Wotschke, D.: On the relation between ambiguity and nondeterminism in finite automata. Inform. Comput. 100, 261\u2013270 (1992)","journal-title":"Inform. Comput."},{"issue":"2","key":"16_CR7","doi-asserted-by":"crossref","first-page":"261","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. Inform. Comput. 86(2), 261\u2013270 (1990)","journal-title":"Inform. Comput."},{"issue":"2","key":"16_CR8","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. Univ. Comput. Sci. 8(2), 193\u2013234 (2002)","journal-title":"J. Univ. Comput. Sci."},{"issue":"3","key":"16_CR9","doi-asserted-by":"crossref","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. Inform. Comput. 209(3), 456\u2013470 (2011)","journal-title":"Inform. Comput."},{"issue":"2","key":"16_CR10","doi-asserted-by":"crossref","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. Inform. Comput. 172(2), 202\u2013217 (2002)","journal-title":"Inform. Comput."},{"issue":"3","key":"16_CR11","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1007\/s00224-010-9277-4","volume":"48","author":"J Hromkovi\u010d","year":"2011","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Ambiguity and communication. Theory Comput. Syst. 48(3), 517\u2013534 (2011)","journal-title":"Theory Comput. Syst."},{"key":"16_CR12","unstructured":"Keeler, C.: New metrics for finite automaton complexity and subregular language hierarchies. QSPACE. \nhttps:\/\/qspace.library.queensu.ca\/handle\/1974\/15329"},{"issue":"4","key":"16_CR13","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1007\/BF01189856","volume":"26","author":"CMR Kintala","year":"1993","unstructured":"Kintala, C.M.R., Pun, K.Y., Wotschke, D.: Concise representations of regular languages by degree and probabilistic finite automata. Math. Syst. Theory 26(4), 379\u2013395 (1993)","journal-title":"Math. Syst. Theory"},{"issue":"4","key":"16_CR14","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1002\/spe.2309","volume":"46","author":"G Lamperti","year":"2016","unstructured":"Lamperti, G., Scandale, M., Zanella, M.: Determinization and minimization of finite acyclic automata by incremental techniques. Softw. Pract. Exp. 46(4), 513\u2013549 (2016)","journal-title":"Softw. Pract. Exp."},{"issue":"4","key":"16_CR15","doi-asserted-by":"crossref","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. 27(4), 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"key":"16_CR16","unstructured":"Msiska, M., van Zijl, L.: Interpreting the subset construction using finite sublanguages. In: Proceedings of Prague Stringology Conference 2016, pp. 48\u201362 (2016)"},{"issue":"2\u20134","key":"16_CR17","first-page":"245","volume":"17","author":"A Palioudakis","year":"2012","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: State complexity of finite tree width NFAs. J. Automata Lang. Comb. 17(2\u20134), 245\u2013264 (2012)","journal-title":"J. Automata Lang. Comb."},{"issue":"2","key":"16_CR18","first-page":"89","volume":"62","author":"A Palioudakis","year":"2015","unstructured":"Palioudakis, A., Salomaa, K., Akl, S.G.: Quantifying nondeterminism in finite automata. Ann. Univ. Bucharest Informatica 62(2), 89\u2013100 (2015)","journal-title":"Ann. Univ. Bucharest Informatica"},{"issue":"6","key":"16_CR19","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM J. Comput. 18(6), 1263\u20131282 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"16_CR20","first-page":"177","volume":"2","author":"K Salomaa","year":"1997","unstructured":"Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets. J. Automata Lang. Comb. 2(3), 177\u2013186 (1997)","journal-title":"J. Automata Lang. Comb."},{"issue":"2","key":"16_CR21","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1006\/inco.1994.1076","volume":"113","author":"J Shallit","year":"1994","unstructured":"Shallit, J.: Numeration systems, linear recurrences, and regular sets. Inf. Comput. 113(2), 331\u2013347 (1994)","journal-title":"Inf. Comput."},{"key":"16_CR22","volume-title":"Second Course in Formal Languages and Automata Theory","author":"J Shallit","year":"2009","unstructured":"Shallit, J.: Second Course in Formal Languages and Automata Theory. Cambridge University Press, Cambridge (2009)"},{"issue":"2","key":"16_CR23","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"16_CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(91)90381-B","volume":"88","author":"A Weber","year":"1991","unstructured":"Weber, A., Seidl, H.: On the degree of ambiguity of finite automata. Theoret. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theoret. Comput. Sci."},{"key":"16_CR25","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-642-59136-5_2","volume-title":"Handbook of Formal Languages","author":"S Yu","year":"1997","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, pp. 41\u2013110. Springer, Heidelberg (1997)"}],"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-60252-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T15:02:56Z","timestamp":1496415776000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}