{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:05:16Z","timestamp":1757624716332,"version":"3.44.0"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032014740"},{"type":"electronic","value":"9783032014757"}],"license":[{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,8,17]],"date-time":"2025-08-17T00:00:00Z","timestamp":1755388800000},"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":[[2026]]},"DOI":"10.1007\/978-3-032-01475-7_12","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T17:39:29Z","timestamp":1755365969000},"page":"166-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Improved Upper Bounds for\u00a0Determinizing NIDPDAs with\u00a0Limited Nondeterminism"],"prefix":"10.1007","author":[{"given":"Mohammad","family":"Zakzok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: ACM Symposium on Theory of Computation, pp. 202\u2013211 (2004)","DOI":"10.1145\/1007352.1007390"},{"key":"12_CR2","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516518"},{"key":"12_CR3","doi-asserted-by":"crossref","unstructured":"Bozzelli, L.: Alternating automata and temporal fixpoint calculus for visibly pushdown automata. In: Concurrency Theory, CONCUR\u201907. Lecture Notes in Computer Science, vol.\u00a04703, pp. 476\u2013491. Springer (2007)","DOI":"10.1007\/978-3-540-74407-8_32"},{"key":"12_CR4","first-page":"1","volume":"24","author":"B von Braunm\u00fchl","year":"1985","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input driven languages are recognized in log $$n$$ space. Ann. Discrete Math. 24, 1\u201320 (1985)","journal-title":"Ann. Discrete Math."},{"key":"12_CR5","unstructured":"Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. The MIT Press (1999)"},{"issue":"5","key":"12_CR6","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00236-020-00373-8","volume":"58","author":"V Geffert","year":"2021","unstructured":"Geffert, V., Kapoutsis, C.A., Zakzok, M.: Complement for two-way alternating automata. Acta Inform. 58(5), 463\u2013495 (2021)","journal-title":"Acta Inform."},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Geffert, V., Kapoutsis, C.A., Zakzok, M.: Improved complement for two-way alternating automata. Acta Inform (2022)","DOI":"10.1007\/s00236-021-00414-w"},{"issue":"2","key":"12_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. 86(2), 179\u2013194 (1990)","journal-title":"Inf. Comput."},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1016\/j.tcs.2022.10.023","volume":"939","author":"YS Han","year":"2023","unstructured":"Han, Y.S., Ko, S.K., Salomaa, K.: Deciding path size of nondeterministic (and input-driven) pushdown automata. Theoret. Comput. Sci. 939, 170\u2013181 (2023)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR10","doi-asserted-by":"publisher","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. Inf. Comput. 172, 202\u2013217 (2002)","journal-title":"Inf. Comput."},{"key":"12_CR11","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-319-98654-8_36","volume-title":"Developments in Language Theory","author":"G Jir\u00e1skov\u00e1","year":"2018","unstructured":"Jir\u00e1skov\u00e1, G., Okhotin, A.: Towards exact state complexity bounds for input-driven pushdown automata. In: Hoshi, M., Seki, S. (eds.) Developments in Language Theory, pp. 441\u2013452. Springer International Publishing, Cham (2018)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/j.tcs.2020.12.011","volume":"870","author":"C Kapoutsis","year":"2021","unstructured":"Kapoutsis, C., Zakzok, M.: Alternation in two-way finite automata. Theoret. Comput. Sci. 870, 75\u2013102 (2021)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1007\/978-3-642-02737-6_4","volume-title":"Developments in Language Theory","author":"CA Kapoutsis","year":"2009","unstructured":"Kapoutsis, C.A.: Size complexity of two-way finite automata. In: Diekert, V., Nowotka, D. (eds.) Developments in Language Theory, pp. 47\u201366. Springer, Berlin Heidelberg, Berlin, Heidelberg (2009)"},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Keeler, C., Salomaa, K.: Structural properties of NFAs and growth rates of nondeterminism measures. Inf. Comput. 284, 104690 (2022)","DOI":"10.1016\/j.ic.2021.104690"},{"key":"12_CR15","unstructured":"Knuth, D.E.: Seminumerical Algorithms, volume 3 of The Art of Computer Programming. Addison-Wesley (1973)"},{"issue":"1","key":"12_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1137\/0213010","volume":"13","author":"R Ladner","year":"1984","unstructured":"Ladner, R., Lipton, R., Stockmeyer, L.: Alternating pushdown and stack automata. SIAM J. Comput. 13(1), 135\u2013155 (1984)","journal-title":"SIAM J. Comput."},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s002360050133","volume":"35","author":"H Leung","year":"1998","unstructured":"Leung, H.: On finite automata with limited nondeterminism. Acta Informatica 35, 595\u2013624 (1998)","journal-title":"Acta Informatica"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Martynova, O.: Exact descriptional complexity of determinization of input-driven pushdown automata. In: Implementation and Application of Automata: 28th International Conference, CIAA 2024, pp. 249\u2013260. Springer-Verlag, Berlin, Heidelberg (2024)","DOI":"10.1007\/978-3-031-71112-1_18"},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL recognition. In: Automata, Languages and Programming, 1980, pp. 422\u2013435. Lecture Notes in Computer Science, Springer (1980)","DOI":"10.1007\/3-540-10003-2_89"},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Okhotin, A., Piao, X., Salomaa, K.: Descriptional complexity of input-driven pushdown automata. In: Languages Alive. Lecture Notes Computer Science, vol.\u00a07300, pp. 186\u2013206. Springer (2012)","DOI":"10.1007\/978-3-642-31644-9_13"},{"issue":"2","key":"12_CR21","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/2636805.2636821","volume":"45","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A., Salomaa, K.: Complexity of input-driven pushdown automata. SIGACT News 45(2), 47\u201367 (2014)","journal-title":"SIGACT News"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-319-09698-8_9","volume-title":"Developments in Language Theory","author":"A Okhotin","year":"2014","unstructured":"Okhotin, A., Salomaa, K.: Input-driven pushdown automata with limited nondeterminism. In: Shur, A.M., Volkov, M.V. (eds.) Developments in Language Theory, pp. 84\u2013102. Springer International Publishing, Cham (2014)"},{"issue":"2\u20134","key":"12_CR23","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. Autom. Lang. Comb. 17(2\u20134), 245\u2013264 (2012)","journal-title":"J. Autom. Lang. Comb."},{"issue":"6","key":"12_CR24","doi-asserted-by":"publisher","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."},{"key":"12_CR25","doi-asserted-by":"publisher","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Proceedings of the Tenth Annual ACM Symposium on Theory of Computing, pp. 275\u2013286. STOC \u201978, Association for Computing Machinery, New York, NY, USA (1978). https:\/\/doi.org\/10.1145\/800133.804357","DOI":"10.1145\/800133.804357"},{"key":"12_CR26","doi-asserted-by":"crossref","unstructured":"Stanley, R.P., Fomin, S.: Trees and the Composition of Generating Functions, pp. 1\u2013158. Cambridge Studies in Advanced Mathematics, Cambridge University Press (1999)","DOI":"10.1017\/CBO9780511609589.004"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01475-7_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T15:14:38Z","timestamp":1757430878000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01475-7_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,17]]},"ISBN":["9783032014740","9783032014757"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01475-7_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025,8,17]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"DLT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Developments in Language Theory","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Seoul","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Korea (Republic of)","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"dlt2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/cida.uos.ac.kr\/dlt2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}