{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T13:28:52Z","timestamp":1725542932600},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540373766"},{"type":"electronic","value":"9783540373773"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11817949_34","type":"book-chapter","created":{"date-parts":[[2006,8,2]],"date-time":"2006-08-02T19:59:29Z","timestamp":1154548769000},"page":"509-523","source":"Crossref","is-referenced-by-count":1,"title":["Second-Order Simple Grammars"],"prefix":"10.1007","author":[{"given":"Colin","family":"Stirling","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"Aehlig, K., De Miranda, J., Ong, C.-H.L.: Safety is not a restriction at level 2 for string languages. LNCS, vol.\u00a03411, pp. 490\u2013511 (2005)","DOI":"10.1007\/978-3-540-31982-5_31"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"647","DOI":"10.1145\/321479.321488","volume":"15","author":"A. Aho","year":"1968","unstructured":"Aho, A.: Indexed grammars\u2013an extension of context-free grammars. Journal of ACM\u00a015, 647\u2013671 (1968)","journal-title":"Journal of ACM"},{"key":"34_CR3","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1145\/321526.321529","volume":"16","author":"A. Aho","year":"1969","unstructured":"Aho, A.: Nested stack automata. Journal of ACM\u00a016, 383\u2013406 (1969)","journal-title":"Journal of ACM"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/174130.174141","volume":"40","author":"J. Baeten","year":"1993","unstructured":"Baeten, J., Bergstra, J., Klop, J.: Decidability of bisimulation equivalence for processes generating context-free languages. Journal of ACM\u00a040, 653\u2013682 (1993)","journal-title":"Journal of ACM"},{"key":"34_CR5","unstructured":"Blumensath, A.: A pumping lemma for higher-order pushdown automata (preprint 2004)"},{"key":"34_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-540-30538-5_12","volume-title":"FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science","author":"A. Bouajjani","year":"2004","unstructured":"Bouajjani, A., Meyer, A.: Symbolic Reachability Analysis of Higher-Order Context-Free Processes. In: Lodaya, K., Mahajan, M. (eds.) FSTTCS 2004. LNCS, vol.\u00a03328, pp. 135\u2013147. Springer, Heidelberg (2004)"},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/B978-044482830-9\/50027-8","volume-title":"Handbook of Process Algebra","author":"O. Burkart","year":"2001","unstructured":"Burkart, O., Caucal, D., Moller, F., Steffen, B.: Verification on infinite structures. In: Bergstra, J., Ponse, A., Smolka, S. (eds.) Handbook of Process Algebra, pp. 545\u2013623. North-Holland, Amsterdam (2001)"},{"key":"34_CR8","doi-asserted-by":"crossref","unstructured":"Cachat, T.: Higher order pushdown automata, the Caucal hierarchy of graphs and parity games. LNCS, vol.\u00a02719, pp. 556\u2013569 (2003)","DOI":"10.1007\/3-540-45061-0_45"},{"key":"34_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/3-540-45687-2_13","volume-title":"Mathematical Foundations of Computer Science 2002","author":"D. Caucal","year":"2002","unstructured":"Caucal, D.: On Infinite Terms Having a Decidable Monadic Theory. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 165\u2013176. Springer, Heidelberg (2002)"},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0304-3975(78)90008-7","volume":"6","author":"B. Courcelle","year":"1978","unstructured":"Courcelle, B.: A representation of trees by languages I and II. Theoretical Computer Science\u00a06, 255\u2013279 and 7, 25\u201355 (1978)","journal-title":"Theoretical Computer Science"},{"key":"34_CR11","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0304-3975(82)90009-3","volume":"25","author":"W. Damm","year":"1982","unstructured":"Damm, W.: The IO- and OI-hierarchy. Theoretical Computer Science\u00a025, 95\u2013169 (1982)","journal-title":"Theoretical Computer Science"},{"key":"34_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(86)80016-X","volume":"71","author":"W. Damm","year":"1986","unstructured":"Damm, W., Goerdt, A.: An automata-theoretical characterization of the OI-hierarchy. Information and Control\u00a071, 1\u201332 (1986)","journal-title":"Information and Control"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0890-5401(91)90015-T","volume":"95","author":"J. Engelfriet","year":"1991","unstructured":"Engelfriet, J.: Iterated stack automata and complexity classes. Information and Computation\u00a095, 21\u201375 (1991)","journal-title":"Information and Computation"},{"key":"34_CR14","doi-asserted-by":"crossref","unstructured":"Fischer, M.: Grammars with macro-like productions. In: Procs. 9th Annual IEEE Symposium on Switching and Automata Theory, pp. 131\u2013142 (1968)","DOI":"10.1109\/SWAT.1968.12"},{"key":"34_CR15","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(76)90074-8","volume":"1","author":"E. Freidman","year":"1976","unstructured":"Freidman, E.: The inclusion problem for simple languages. Theoretical Computer Science\u00a01, 297\u2013316 (1976)","journal-title":"Theoretical Computer Science"},{"key":"34_CR16","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(96)00244-7","volume":"163","author":"R. Gilman","year":"1996","unstructured":"Gilman, R.: A shrinking lemma for indexed languages. Theoretical Computer Science\u00a0163, 277\u2013281 (1996)","journal-title":"Theoretical Computer Science"},{"key":"34_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/11690634_19","volume-title":"Foundations of Software Science and Computation Structures","author":"P. Jan\u010dar","year":"2006","unstructured":"Jan\u010dar, P., Srba, J.: Undecidability results for bisimilarity on prefix rewrite systems. In: Aceto, L., Ing\u00f3lfsd\u00f3ttir, A. (eds.) FOSSACS 2006. LNCS, vol.\u00a03921, pp. 277\u2013291. Springer, Heidelberg (2006)"},{"key":"34_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-45931-6_15","volume-title":"Foundations of Software Science and Computation Structures","author":"T. Knapik","year":"2002","unstructured":"Knapik, T., Niwi\u0144ski, D., Urzyczyn, P.: Higher-order pushdown trees are easy. In: Nielsen, M., Engberg, U. (eds.) FOSSACS 2002. LNCS, vol.\u00a02303, pp. 205\u2013222. Springer, Heidelberg (2002)"},{"key":"34_CR19","doi-asserted-by":"crossref","unstructured":"Korenjak, A., Hopcroft, J.: Simple deterministic languages. In: Procs. 7th Annual IEEE Symposium on Switching and Automata Theory, pp. 36\u201346 (1966)","DOI":"10.1109\/SWAT.1966.22"},{"key":"34_CR20","first-page":"38","volume":"12","author":"A. Maslov","year":"1976","unstructured":"Maslov, A.: Multilevel stack automata. Problems of Information Transmission\u00a012, 38\u201343 (1976)","journal-title":"Problems of Information Transmission"},{"key":"34_CR21","unstructured":"Ong, C.-H.L.: On model-checking trees generated by higher-order recursion schemes (preprint 2006)"},{"key":"34_CR22","doi-asserted-by":"publisher","first-page":"48","DOI":"10.1016\/S0019-9958(80)90867-0","volume":"45","author":"R. Parchmann","year":"1980","unstructured":"Parchmann, R., Duske, J., Specht, J.: On deterministic indexed languages. Information and Control\u00a045, 48\u201367 (1980)","journal-title":"Information and Control"},{"key":"34_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00285-1","volume":"251","author":"G. S\u00e9nizergues","year":"2001","unstructured":"S\u00e9nizergues, G.: L(A) = L(B)? decidability results from complete formal systems. Theoretical Computer Science\u00a0251, 1\u2013166 (2001)","journal-title":"Theoretical Computer Science"},{"key":"34_CR24","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1016\/S0304-3975(02)00027-0","volume":"281","author":"G. S\u00e9nizergues","year":"2002","unstructured":"S\u00e9nizergues, G.: L(A) = L(B)? a simplified decidability proof. Theoretical Computer Science\u00a0281, 555\u2013608 (2002)","journal-title":"Theoretical Computer Science"},{"key":"34_CR25","doi-asserted-by":"crossref","unstructured":"S\u00e9nizergues, G.:The equivalence problem for t-turn DPDA is co-NP. LNCS, vol.\u00a02719, pp. 478\u2013489 (2003)","DOI":"10.1007\/3-540-45061-0_39"},{"key":"34_CR26","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1137\/S0097539700377256","volume":"34","author":"G. S\u00e9nizergues","year":"2005","unstructured":"S\u00e9nizergues, G.: The bisimulation problem for equational graphs of finite out-degree. SIAM Journal of Computing\u00a034, 1025\u20131106 (2005)","journal-title":"SIAM Journal of Computing"},{"key":"34_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(00)00389-3","volume":"255","author":"C. Stirling","year":"2001","unstructured":"Stirling, C.: Decidability of DPDA equivalence. Theoretical Computer Science\u00a0255, 1\u201331 (2001)","journal-title":"Theoretical Computer Science"},{"key":"34_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1007\/3-540-45465-9_70","volume-title":"Automata, Languages and Programming","author":"C. Stirling","year":"2002","unstructured":"Stirling, C.: Deciding DPDA equivalence is primitive recursive. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 821\u2013832. Springer, Heidelberg (2002)"},{"key":"34_CR29","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/BF01191624","volume":"27","author":"K. Vijay-Shanker","year":"1994","unstructured":"Vijay-Shanker, K., Weir, D.: The equivalence of four extensions of context-free grammars. Mathematical Systems Theory\u00a027, 511\u2013546 (1994)","journal-title":"Mathematical Systems Theory"}],"container-title":["Lecture Notes in Computer Science","CONCUR 2006 \u2013 Concurrency Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11817949_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:15:52Z","timestamp":1605644152000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11817949_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540373766","9783540373773"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/11817949_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}