{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T03:31:14Z","timestamp":1767929474441,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662476659","type":"print"},{"value":"9783662476666","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_35","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T03:46:47Z","timestamp":1434685607000},"page":"440-451","source":"Crossref","is-referenced-by-count":20,"title":["An Approach to Computing Downward Closures"],"prefix":"10.1007","author":[{"given":"Georg","family":"Zetzsche","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"35_CR1","doi-asserted-by":"crossref","unstructured":"Abdulla, P.A., Boasson, L., Bouajjani, A.: Effective lossy queue languages. In: Proc. of ICALP 2001, pp. 639\u2013651 (2001)","DOI":"10.1007\/3-540-48224-5_53"},{"issue":"1","key":"35_CR2","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1023\/B:FORM.0000033962.51898.1a","volume":"25","author":"PA Abdulla","year":"2004","unstructured":"Abdulla, P.A., Collomb-Annichini, A., Bouajjani, A., Jonsson, B.: Using Forward Reachability Analysis for Verification of Lossy Channel Sys- tems. Form. Method. Syst. Des. 25(1), 39\u201365 (2004)","journal-title":"Form. Method. Syst. Des."},{"issue":"4","key":"35_CR3","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"AV Aho","year":"1968","unstructured":"Aho, A.V.: Indexed grammars-an extension of context-free grammars. J. ACM 15(4), 647\u2013671 (1968)","journal-title":"J. ACM"},{"key":"35_CR4","doi-asserted-by":"crossref","unstructured":"Bonnet, R., Finkel, A., Leroux, J., Zeitoun, M.: Model Checking Vector Addition Systems with one zero-test. In: LMCS 8.2:11 (2012)","DOI":"10.2168\/LMCS-8(2:11)2012"},{"key":"35_CR5","doi-asserted-by":"crossref","unstructured":"Bouajjani, A., Esparza, J., Maler, O.: Reachability analysis of push- down automata: application to model-checking. In: Proc. of CONCUR 1997, pp. 135\u2013150 (1997)","DOI":"10.1007\/3-540-63141-0_10"},{"key":"35_CR6","doi-asserted-by":"crossref","unstructured":"Colcombet, T.: Regular cost functions, Part I: logic and algebra over words. In: LMCS 9.3 (2013)","DOI":"10.2168\/LMCS-9(3:3)2013"},{"key":"35_CR7","first-page":"178","volume":"44","author":"B Courcelle","year":"1991","unstructured":"Courcelle, B.: On constructing obstruction sets of words. Bulletin of the EATCS 44, 178\u2013186 (1991)","journal-title":"Bulletin of the EATCS"},{"key":"35_CR8","unstructured":"Czerwi\u0144ski, W., Martens, W.: A Note on Decidable Separability by Piece- wise Testable Languages (2014). \n                      arXiv:1410.1042\n                      \n                     [cs.FL]"},{"key":"35_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-74932-2","volume-title":"Regulated rewriting in formal language theory","author":"J Dassow","year":"1989","unstructured":"Dassow, J., P\u0103un, G.: Regulated rewriting in formal language theory. Springer-Verlag, Berlin (1989)"},{"key":"35_CR10","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/978-3-662-07675-0_3","volume-title":"Handbook of Formal Languages","author":"J Dassow","year":"1997","unstructured":"Dassow, J., P\u0103un, G., Salomaa, A.: Grammars with controlled derivations. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 2, pp. 101\u2013154. Springer, Heidelberg (1997)"},{"issue":"4","key":"35_CR11","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1016\/0304-3975(76)90076-1","volume":"1","author":"A Ehrenfeucht","year":"1976","unstructured":"Ehrenfeucht, A., Rozenberg, G., Skyum, S.: A relationship between ET0L and EDT0L languages. Theor. Comput. Sci. 1(4), 325\u2013330 (1976)","journal-title":"Theor. Comput. Sci."},{"issue":"1-2","key":"35_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(96)00244-7","volume":"163","author":"RH Gilman","year":"1996","unstructured":"Gilman, R.H.: A shrinking lemma for indexed languages. Theor. Comput. Sci. 163(1-2), 277\u2013281 (1996)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"35_CR13","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.tcs.2007.07.036","volume":"387","author":"H Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M., Kutrib, M.: The size of Higman-Haines sets. Theor. Comput. Sci. 387(2), 167\u2013176 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-642-14162-1_39","volume-title":"Automata, Languages and Programming","author":"P Habermehl","year":"2010","unstructured":"Habermehl, P., Meyer, R., Wimmel, H.: The downward-closure of petri net languages. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6199, pp. 466\u2013477. Springer, Heidelberg (2010)"},{"issue":"1","key":"35_CR15","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1016\/S0021-9800(69)80111-0","volume":"6","author":"LH Haines","year":"1969","unstructured":"Haines, L.H.: On free monoids partially ordered by embedding. J. Combin. Theory 6(1), 94\u201398 (1969)","journal-title":"J. Combin. Theory"},{"issue":"1","key":"35_CR16","doi-asserted-by":"publisher","first-page":"61","DOI":"10.2977\/prims\/1195192738","volume":"9","author":"T Hayashi","year":"1973","unstructured":"Hayashi, T.: On Derivation Trees of Indexed Grammars-An Extension of the uvwxy-Theorem\u2013. Publications of the Research Institute for Mathematical Sciences 9(1), 61\u201392 (1973)","journal-title":"Publications of the Research Institute for Mathematical Sciences"},{"key":"35_CR17","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Reading (1979)"},{"issue":"1","key":"35_CR18","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1051\/ita\/1979130100191","volume":"13","author":"M Jantzen","year":"1979","unstructured":"Jantzen, M.: On the hierarchy of Petri net languages. RAIRO Theor. Inf. Appl. 13(1), 19\u201330 (1979)","journal-title":"RAIRO Theor. Inf. Appl."},{"key":"35_CR19","unstructured":"Jullien, P.: Contribution \u00e0 l\u00e9tude des types d\u2019ordres dispers\u00e9s. Universit\u00e9 de Marseille, PhD thesis (1969)"},{"key":"35_CR20","unstructured":"Kartzow, A.: A pumping lemma for collapsible pushdown graphs of level 2. In: Proc. of CSL 2011, pp. 322\u2013336 (2011)"},{"issue":"3","key":"35_CR21","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1016\/0012-365X(78)90156-5","volume":"21","author":"J Leeuwen van","year":"1978","unstructured":"van Leeuwen, J.: Effective constructions in well-partially-ordered free monoids. Discrete Math. 21(3), 237\u2013252 (1978)","journal-title":"Discrete Math."},{"issue":"1","key":"35_CR22","first-page":"38","volume":"12","author":"AN Maslov","year":"1976","unstructured":"Maslov, A.N.: Multilevel stack automata. Problems of Information Transmission 12(1), 38\u201342 (1976)","journal-title":"Problems of Information Transmission"},{"issue":"1-3","key":"35_CR23","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0304-3975(02)00646-1","volume":"297","author":"R Mayr","year":"2003","unstructured":"Mayr, R.: Undecidable problems in unreliable computations. Theor. Comput. Sci. 297(1-3), 337\u2013354 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR24","unstructured":"Parys, P.: A pumping lemma for pushdown graphs of any level. In: Proc. of STACS 2012, pp. 54\u201365 (2012)"},{"key":"35_CR25","doi-asserted-by":"crossref","unstructured":"Rounds, W.C.: Tree-oriented proofs of some theorems on context-free and indexed languages. In: Proc. of STOC 1970, pp. 109\u2013116 (1970)","DOI":"10.1145\/800161.805156"},{"issue":"2","key":"35_CR26","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","volume":"88","author":"H Seki","year":"1991","unstructured":"Seki, H., Matsumura, T., Fujii, M., Kasami, T.: On multiple context-free grammars. Theor. Comput. Sci. 88(2), 191\u2013229 (1991)","journal-title":"Theor. Comput. Sci."},{"key":"35_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/978-3-662-44522-8_43","volume-title":"Mathematical Foundations of Computer Science 2014","author":"T Smith","year":"2014","unstructured":"Smith, T.: On infinite words determined by indexed languages. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014, Part I. LNCS, vol. 8634, pp. 511\u2013522. Springer, Heidelberg (2014)"},{"key":"35_CR28","unstructured":"Zetzsche, G.: An approach to computing downward closures (2015). arXiv:1503. 01068 [cs.FL]"},{"key":"35_CR29","unstructured":"Zetzsche, G.: Computing downward closures for stacked counter au tomata. In: Proc. of STACS 2015, pp. 743\u2013756 (2015)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T03:15:57Z","timestamp":1559186157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]}}}