{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T04:57:44Z","timestamp":1695272264307},"reference-count":18,"publisher":"World Scientific Pub Co Pte Ltd","issue":"06n07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,9]]},"abstract":"<jats:p>The quotient of a formal language [Formula: see text] by another language [Formula: see text] is the set of all strings obtained by taking a string from [Formula: see text] that ends with a suffix of a string from [Formula: see text], and removing that suffix. The quotient of a regular language by any language is always regular, whereas the context-free languages and many of their subfamilies, such as the linear and the deterministic languages, are not closed under the quotient operation. This paper establishes the closure of the family of languages recognized by input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, under the quotient operation. A construction of automata representing the result of the operation is given, and its state complexity with respect to nondeterministic IDPDA is shown to be exactly [Formula: see text], where [Formula: see text] and [Formula: see text] are the numbers of states in the automata recognizing [Formula: see text] and [Formula: see text], respectively.<\/jats:p>","DOI":"10.1142\/s0129054119400367","type":"journal-article","created":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T07:06:43Z","timestamp":1568876803000},"page":"1217-1235","source":"Crossref","is-referenced-by-count":0,"title":["State Complexity of the Quotient Operation on Input-Driven Pushdown Automata"],"prefix":"10.1142","volume":"30","author":[{"given":"Alexander","family":"Okhotin","sequence":"first","affiliation":[{"name":"St. Petersburg State University, 7\/9 Universitetskaya nab., Saint Petersburg 199034, Russia"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[{"name":"School of Computing, Queen\u2019s University, Kingston, Ontario K7L 2N8, Canada"}]}],"member":"219","published-online":{"date-parts":[[2019,9,19]]},"reference":[{"key":"S0129054119400367BIB001","first-page":"202","volume-title":"ACM Symposium on Theory of Computing","author":"Alur R."},{"key":"S0129054119400367BIB002","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516518"},{"key":"S0129054119400367BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"S0129054119400367BIB004","first-page":"1","volume":"24","author":"von Braunm\u00fchl B.","year":"1985","journal-title":"Annals of Discrete Mathematics"},{"key":"S0129054119400367BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80019-0"},{"key":"S0129054119400367BIB006","doi-asserted-by":"publisher","DOI":"10.1145\/321186.321191"},{"key":"S0129054119400367BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.01.004"},{"key":"S0129054119400367BIB008","first-page":"42","volume-title":"Proceedings of Symposia in Applied Mathematics","volume":"19","author":"Hartmanis J.","year":"1967"},{"issue":"5","key":"S0129054119400367BIB009","doi-asserted-by":"crossref","first-page":"579","DOI":"10.1007\/BF00267045","volume":"22","author":"Latteux M.","year":"1985","journal-title":"Acta Informatica"},{"key":"S0129054119400367BIB010","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/3-540-10003-2_89","volume-title":"Automata, Languages and Programming","volume":"85","author":"Mehlhorn K."},{"key":"S0129054119400367BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.01.007"},{"key":"S0129054119400367BIB012","doi-asserted-by":"publisher","DOI":"10.1145\/2636805.2636821"},{"key":"S0129054119400367BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.11.015"},{"key":"S0129054119400367BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.02.001"},{"key":"S0129054119400367BIB015","series-title":"LNCS","first-page":"260","volume-title":"Computer Science in Russia","volume":"10304","author":"Okhotin A."},{"key":"S0129054119400367BIB016","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/978-3-319-60252-3_24","volume-title":"Descriptional Complexity of Formal Systems","volume":"10316","author":"Okhotin A."},{"key":"S0129054119400367BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.05.002"},{"key":"S0129054119400367BIB018","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/14.4.396"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054119400367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T13:36:46Z","timestamp":1695217006000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054119400367"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9]]},"references-count":18,"journal-issue":{"issue":"06n07","published-print":{"date-parts":[[2019,9]]}},"alternative-id":["10.1142\/S0129054119400367"],"URL":"https:\/\/doi.org\/10.1142\/s0129054119400367","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9]]}}}