{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,1]],"date-time":"2025-12-01T02:50:58Z","timestamp":1764557458147,"version":"3.40.3"},"publisher-location":"Cham","reference-count":17,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319986531"},{"type":"electronic","value":"9783319986548"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-98654-8_41","type":"book-chapter","created":{"date-parts":[[2018,8,4]],"date-time":"2018-08-04T19:43:57Z","timestamp":1533411837000},"page":"503-515","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On Finitely Ambiguous B\u00fcchi Automata"],"prefix":"10.1007","author":[{"given":"Christof","family":"L\u00f6ding","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anton","family":"Pirogov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,8,5]]},"reference":[{"key":"41_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/978-3-540-85780-8_8","volume-title":"Developments in Language Theory","author":"C Allauzen","year":"2008","unstructured":"Allauzen, C., Mohri, M., Rastogi, A.: General algorithms for testing the ambiguity of finite automata. In: Ito, M., Toyama, M. (eds.) DLT 2008. LNCS, vol. 5257, pp. 108\u2013120. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-85780-8_8"},{"issue":"1\u20132","key":"41_CR2","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0304-3975(83)90086-5","volume":"26","author":"A Arnold","year":"1983","unstructured":"Arnold, A.: Rational $$\\omega $$ -languages are non-ambiguous. Theor. Comput. Sci. 26(1\u20132), 221\u2013223 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"41_CR3","volume-title":"Principles of Model Checking","author":"C Baier","year":"2008","unstructured":"Baier, C., Katoen, J.: Principles of Model Checking. MIT Press, Cambridge (2008)"},{"key":"41_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-319-41528-4_2","volume-title":"Computer Aided Verification","author":"C Baier","year":"2016","unstructured":"Baier, C., Kiefer, S., Klein, J., Kl\u00fcppelholz, S., M\u00fcller, D., Worrell, J.: Markov chains and unambiguous B\u00fcchi automata. In: Chaudhuri, S., Farzan, A. (eds.) CAV 2016. LNCS, vol. 9779, pp. 23\u201342. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-41528-4_2"},{"key":"41_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-642-13089-2_10","volume-title":"Language and Automata Theory and Applications","author":"N Bousquet","year":"2010","unstructured":"Bousquet, N., L\u00f6ding, C.: Equivalence and inclusion problem for strongly unambiguous B\u00fcchi automata. In: Dediu, A.-H., Fernau, H., Mart\u00edn-Vide, C. (eds.) LATA 2010. LNCS, vol. 6031, pp. 118\u2013129. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13089-2_10"},{"key":"41_CR6","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: On a decision method in restricted second order arithmetic. In: Studies in Logic and the Foundations of Mathematics, vol. 44, pp. 1\u201311. Elsevier (1966)","DOI":"10.1016\/S0049-237X(09)70564-6"},{"issue":"1","key":"41_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(88)90012-6","volume":"23","author":"TH Chan","year":"1988","unstructured":"Chan, T.H., Ibarra, O.H.: On the finite-valuedness problem for sequential machines. Theor. Comput. Sci. 23(1), 95\u2013101 (1988)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"41_CR8","doi-asserted-by":"publisher","first-page":"857","DOI":"10.1145\/210332.210339","volume":"42","author":"C Courcoubetis","year":"1995","unstructured":"Courcoubetis, C., Yannakakis, M.: The complexity of probabilistic verification. J. ACM 42(4), 857\u2013907 (1995)","journal-title":"J. ACM"},{"key":"41_CR9","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/978-3-540-39813-4_26","volume-title":"Logic for Programming, Artificial Intelligence, and Reasoning","author":"J-M Couvreur","year":"2003","unstructured":"Couvreur, J.-M., Saheb, N., Sutre, G.: An optimal automata approach to LTL model checking of probabilistic systems. In: Vardi, M.Y., Voronkov, A. (eds.) LPAR 2003. LNCS (LNAI), vol. 2850, pp. 361\u2013375. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-39813-4_26"},{"issue":"14\u201315","key":"41_CR10","doi-asserted-by":"publisher","first-page":"578","DOI":"10.1016\/j.ipl.2012.04.010","volume":"112","author":"D Isaak","year":"2012","unstructured":"Isaak, D., L\u00f6ding, C.: Efficient inclusion testing for simple classes of unambiguous $$\\omega $$ -automata. Inf. Process. Lett. 112(14\u201315), 578\u2013582 (2012)","journal-title":"Inf. Process. Lett."},{"key":"41_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/978-3-540-70575-8_59","volume-title":"Automata, Languages and Programming","author":"D K\u00e4hler","year":"2008","unstructured":"K\u00e4hler, D., Wilke, T.: Complementation, disambiguation, and determinization of B\u00fcchi automata unified. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 724\u2013735. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70575-8_59"},{"key":"41_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-319-02444-8_5","volume-title":"Automated Technology for Verification and Analysis","author":"H Karmarkar","year":"2013","unstructured":"Karmarkar, H., Joglekar, M., Chakraborty, S.: Improved upper and lower bounds for B\u00fcchi disambiguation. In: Van Hung, D., Ogawa, M. (eds.) ATVA 2013. LNCS, vol. 8172, pp. 40\u201354. Springer, Cham (2013). https:\/\/doi.org\/10.1007\/978-3-319-02444-8_5"},{"issue":"4","key":"41_CR13","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. 27(4), 1073\u20131082 (1998)","journal-title":"SIAM J. Comput."},{"key":"41_CR14","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of omega-automata. In: Foundations of Computer Science 29th Annual Symposium on 1988, pp. 319\u2013327. IEEE (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"issue":"3","key":"41_CR15","doi-asserted-by":"publisher","first-page":"598","DOI":"10.1137\/0214044","volume":"14","author":"RE 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 J. Comput. 14(3), 598\u2013611 (1985)","journal-title":"SIAM J. Comput."},{"key":"41_CR16","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-642-59126-6_7","volume-title":"Handbook of Formal Languages","author":"W Thomas","year":"1997","unstructured":"Thomas, W.: Languages, Automata, and Logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, pp. 389\u2013455. Springer, Heidelberg (1997). https:\/\/doi.org\/10.1007\/978-3-642-59126-6_7"},{"issue":"2","key":"41_CR17","doi-asserted-by":"publisher","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. Theor. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-98654-8_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,21]],"date-time":"2019-10-21T17:27:42Z","timestamp":1571678862000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-98654-8_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319986531","9783319986548"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-98654-8_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]}}}