{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:07Z","timestamp":1759638547053},"publisher-location":"Cham","reference-count":18,"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_24","type":"book-chapter","created":{"date-parts":[[2017,6,2]],"date-time":"2017-06-02T10:59:13Z","timestamp":1496401153000},"page":"299-310","source":"Crossref","is-referenced-by-count":4,"title":["The Quotient Operation on Input-Driven Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Visibly pushdown languages. In: ACM Symposium on Theory of Computing, STOC 2004, Chicago, USA, pp. 202\u2013211, 13\u201316 June 2004","DOI":"10.1145\/1007352.1007390"},{"key":"24_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/1516512.1516518","volume":"56","author":"R Alur","year":"2009","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. J. ACM 56, 3 (2009)","journal-title":"J. ACM"},{"key":"24_CR3","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0020-0190(92)90198-5","volume":"43","author":"J-C Birget","year":"1992","unstructured":"Birget, J.-C.: Intersection and union of regular languages and state complexity. Inf. Process. Lett. 43, 185\u2013190 (1992)","journal-title":"Inf. Process. Lett."},{"key":"24_CR4","first-page":"1","volume":"24","author":"B Braunm\u00fchl von","year":"1985","unstructured":"von Braunm\u00fchl, B., Verbeek, R.: Input driven languages are recognized in $$\\log n$$ space. Ann. Discret. Math. 24, 1\u201320 (1985)","journal-title":"Ann. Discret. Math."},{"issue":"6","key":"24_CR5","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/S0019-9958(66)80019-0","volume":"9","author":"S Ginsburg","year":"1966","unstructured":"Ginsburg, S., Greibach, S.A.: Deterministic context-free languages. Inf. Control 9(6), 620\u2013648 (1966)","journal-title":"Inf. Control"},{"issue":"4","key":"24_CR6","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1145\/321186.321191","volume":"10","author":"S Ginsburg","year":"1963","unstructured":"Ginsburg, S., Spanier, E.H.: Quotients of context-free languages. J. ACM 10(4), 487\u2013492 (1963)","journal-title":"J. ACM"},{"key":"24_CR7","doi-asserted-by":"crossref","first-page":"2961","DOI":"10.1016\/j.tcs.2009.01.004","volume":"410","author":"Y-S Han","year":"2009","unstructured":"Han, Y.-S., Salomaa, K.: Nondeterministic state complexity of nested word automata. Theoret. Comput. Sci. 410, 2961\u20132971 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Hartmanis, J.: Context-free languages and Turing machine computations. In: Proceedings of Symposia in Applied Mathematics, vol. 19, pp. 42\u201351. AMS (1967)","DOI":"10.1090\/psapm\/019\/0235938"},{"issue":"5","key":"24_CR9","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/BF00267045","volume":"22","author":"M Latteux","year":"1985","unstructured":"Latteux, M., Leguy, B., Ratoandromanana, B.: The family of one-counter languages is closed under quotient. Acta Inform. 22(5), 579\u2013588 (1985)","journal-title":"Acta Inform."},{"key":"24_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","author":"K Mehlhorn","year":"1980","unstructured":"Mehlhorn, K.: Pebbling mountain ranges and its application to DCFL-recognition. In: Bakker, J., Leeuwen, J. (eds.) ICALP 1980. LNCS, vol. 85, pp. 422\u2013435. Springer, Heidelberg (1980). doi: 10.1007\/3-540-10003-2_89"},{"key":"24_CR11","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/j.tcs.2016.01.007","volume":"618","author":"A Okhotin","year":"2016","unstructured":"Okhotin, A.: Input-driven languages are linear conjunctive. Theoret. Comput. Sci. 618, 52\u201371 (2016)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"24_CR12","doi-asserted-by":"crossref","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":"24_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.11.015","volume":"566","author":"A Okhotin","year":"2015","unstructured":"Okhotin, A., Salomaa, K.: Descriptional complexity of unambiguous input-driven pushdown automata. Theoret. Comput. Sci. 566, 1\u201311 (2015)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR14","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/j.jcss.2017.02.001","volume":"86","author":"A Okhotin","year":"2017","unstructured":"Okhotin, A., Salomaa, K.: State complexity of operations on input-driven pushdown automata. J. Comput. Syst. Sci. 86, 207\u2013228 (2017)","journal-title":"J. Comput. Syst. Sci."},{"key":"24_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1007\/978-3-319-58747-9_23","volume-title":"Computer Science - Theory and Applications","author":"A Okhotin","year":"2017","unstructured":"Okhotin, A., Salomaa, K.: Edit distance neighbourhoods of input-driven pushdown automata. In: Weil, P. (ed.) CSR 2017. LNCS, vol. 10304, pp. 260\u2013272. Springer, Cham (2017). doi: 10.1007\/978-3-319-58747-9_23"},{"key":"24_CR16","doi-asserted-by":"crossref","first-page":"3290","DOI":"10.1016\/j.tcs.2009.05.002","volume":"410","author":"X Piao","year":"2009","unstructured":"Piao, X., Salomaa, K.: Operational state complexity of nested word automata. Theoret. Comput. Sci. 410, 3290\u20133302 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR17","doi-asserted-by":"crossref","first-page":"580","DOI":"10.1016\/j.ic.2010.11.021","volume":"209","author":"K Salomaa","year":"2011","unstructured":"Salomaa, K.: Limitations of lower bound methods for deterministic nested word automata. Inf. Comput. 209, 580\u2013589 (2011)","journal-title":"Inf. Comput."},{"issue":"4","key":"24_CR18","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1093\/comjnl\/14.4.396","volume":"14","author":"D Wood","year":"1971","unstructured":"Wood, D.: A further note on top-down deterministic languages. Comput. J. 14(4), 396\u2013403 (1971)","journal-title":"Comput. J."}],"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_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,23]],"date-time":"2023-08-23T18:00:20Z","timestamp":1692813620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-60252-3_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319602516","9783319602523"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-60252-3_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}