{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T01:07:37Z","timestamp":1767229657205,"version":"3.48.0"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030934880"},{"type":"electronic","value":"9783030934897"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-93489-7_15","type":"book-chapter","created":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:30:01Z","timestamp":1640997001000},"page":"176-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Image-Binary Automata"],"prefix":"10.1007","author":[{"given":"Stefan","family":"Kiefer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Cas","family":"Widdershoven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,1,1]]},"reference":[{"key":"15_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-642-24372-1_37","volume-title":"Automated Technology for Verification and Analysis","author":"S Almagor","year":"2011","unstructured":"Almagor, S., Boker, U., Kupferman, O.: What\u2019s decidable about weighted automata? In: Bultan, T., Hsiung, P.-A. (eds.) ATVA 2011. LNCS, vol. 6996, pp. 482\u2013491. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-24372-1_37"},{"key":"15_CR2","unstructured":"Angluin, D., Antonopoulos, T., Fisman, D.: Strongly unambiguous B\u00fcchi automata are polynomially predictable with membership queries. In: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) (2020)"},{"key":"15_CR3","doi-asserted-by":"crossref","unstructured":"Baier, C., Kiefer, S., Klein, J., Kl\u00fcppelholz, S., M\u00fcller, D., Worrell, J.: Markov chains and unambiguous B\u00fcchi automata (extended version of a CAV\u201916 paper). arXiv:1605.00950 (2016), http:\/\/arxiv.org\/abs\/1605.00950","DOI":"10.1007\/978-3-319-41528-4_2"},{"key":"15_CR4","unstructured":"Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Springer, Heidelberg (1988)"},{"issue":"1","key":"15_CR5","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/S0022-0000(71)80005-3","volume":"5","author":"JW Carlyle","year":"1971","unstructured":"Carlyle, J.W., Paz, A.: Realizations by stochastic finite automata. J. Comput. Syst. Sci. 5(1), 26\u201340 (1971)","journal-title":"J. Comput. Syst. Sci."},{"key":"15_CR6","doi-asserted-by":"crossref","unstructured":"Colcombet, T.: Unambiguity in automata theory. In: 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS) (2015)","DOI":"10.1007\/978-3-319-19225-3_1"},{"key":"15_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5","volume-title":"Handbook of Weighted Automata","author":"M Droste","year":"2009","unstructured":"Droste, M., Kuich, W., Vogler, H.: Handbook of Weighted Automata, 1st edn. Springer, Berlin (2009). https:\/\/doi.org\/10.1007\/978-3-642-01492-5","edition":"1"},{"key":"15_CR8","doi-asserted-by":"crossref","unstructured":"Droste, M., Meinecke, I.: Weighted automata and regular expressions over valuation monoids. Int. J. Found. Comput. Sci. 22(08), 1829\u20131844 (2011)","DOI":"10.1142\/S0129054111009069"},{"issue":"4","key":"15_CR9","doi-asserted-by":"publisher","first-page":"10","DOI":"10.1145\/3157831.3157833","volume":"4","author":"N Fijalkow","year":"2017","unstructured":"Fijalkow, N.: Undecidability results for probabilistic automata. ACM SIGLOG News 4(4), 10\u201317 (2017)","journal-title":"ACM SIGLOG News"},{"key":"15_CR10","unstructured":"Filiot, E., Gentilini, R., Raskin, J.F.: Finite-valued weighted automata. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) (2014)"},{"key":"15_CR11","first-page":"197","volume":"53","author":"M Fliess","year":"1974","unstructured":"Fliess, M.: Matrices de Hankel. J. Math. Pures Appl. 53, 197\u2013222 (1974)","journal-title":"J. Math. Pures Appl."},{"key":"15_CR12","unstructured":"Golomb, S.W., Goldstein, R.M., Hales, A.W., Welch, L.R.: Shift Register Sequences. Holden-Day Series in Information Systems, Holden-Day, San Francisco (1967)"},{"key":"15_CR13","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Nondeterministic descriptional complexity of regular languages. Int. J. Found. Comput. Sci. 14, 1087\u20131102 (2003)","DOI":"10.1142\/S0129054103002199"},{"key":"15_CR14","doi-asserted-by":"crossref","unstructured":"Indzhev, E., Kiefer, S.: On complementing unambiguous automata and graphs with many cliques and cocliques. arXiv preprint arXiv:2105.07470 (2021)","DOI":"10.1016\/j.ipl.2022.106270"},{"issue":"5","key":"15_CR15","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1142\/S012905411842008X","volume":"29","author":"J Jir\u00e1sek","year":"2018","unstructured":"Jir\u00e1sek, J., Jir\u00e1skov\u00e1, G., Sebej, J.: Operations on unambiguous finite automata. Int. J. Found. Comput. Sci. 29(5), 861\u2013876 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"15_CR16","doi-asserted-by":"crossref","unstructured":"Karmarkar, H., Joglekar, M., Chakraborty, S.: Improved upper and lower bounds for B\u00fcchi disambiguation. In: Proceedings of the Automated Technology for Verification and Analysis - 11th International Symposium, ATVA 2013 (2013)","DOI":"10.1007\/978-3-319-02444-8_5"},{"key":"15_CR17","unstructured":"Kiefer, S., Widdershoven, C.: Image-binary automata (extended version of a DCFS\u201921 paper). arXiv:2109.01049 (2021), http:\/\/arxiv.org\/abs\/2109.01049"},{"issue":"5","key":"15_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. 16(5), 975\u2013984 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"15_CR19","doi-asserted-by":"publisher","unstructured":"L\u00f6ding, C., Pirogov, A.: On finitely ambiguous B\u00fcchi automata. In: International Conference on Developments in Language Theory, LNCS, pp. 503\u2013515. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-09698-8","DOI":"10.1007\/978-3-319-09698-8"},{"key":"15_CR20","volume-title":"Computational Complexity","author":"CM Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.M.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"15_CR21","unstructured":"Paz, A.: Introduction to Probabilistic Automata. Academic Press, New York (2014)"},{"issue":"3","key":"15_CR22","doi-asserted-by":"publisher","first-page":"230","DOI":"10.1016\/S0019-9958(63)90290-0","volume":"6","author":"MO Rabin","year":"1963","unstructured":"Rabin, M.O.: Probabilistic automata. Inf. Control 6(3), 230\u2013245 (1963)","journal-title":"Inf. Control"},{"key":"15_CR23","unstructured":"Raskin, M.: A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (2018)"},{"key":"15_CR24","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of omega-automata. In: Proceedings of the 27th Annual IEEE Symposium on Logic in Computer Science, pp. 319\u2013327 (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"issue":"2","key":"15_CR25","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0019-9958(61)80020-X","volume":"4","author":"M Sch\u00fctzenberger","year":"1961","unstructured":"Sch\u00fctzenberger, M.: On the definition of a family of automata. Inf. Control 4(2), 245\u2013270 (1961)","journal-title":"Inf. Control"},{"issue":"1","key":"15_CR26","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/0020-0190(96)00039-7","volume":"58","author":"WG Tzeng","year":"1996","unstructured":"Tzeng, W.G.: On path equivalence of nondeterministic finite automata. Inf. Process. Lett. 58(1), 43\u201346 (1996)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"15_CR27","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. Theoret. Comput. Sci. 88(2), 325\u2013349 (1991)","journal-title":"Theoret. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Descriptional Complexity of Formal Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-93489-7_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T01:02:35Z","timestamp":1767229355000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-93489-7_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030934880","9783030934897"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-93489-7_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"1 January 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DCFS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Descriptional Complexity of Formal Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"5 September 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dcfs2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/toc.yonsei.ac.kr\/dcfs2021\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}