{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:17:31Z","timestamp":1760203051966},"publisher-location":"Cham","reference-count":14,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319230207"},{"type":"electronic","value":"9783319230214"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-23021-4_16","type":"book-chapter","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T16:47:30Z","timestamp":1441730850000},"page":"176-188","source":"Crossref","is-referenced-by-count":0,"title":["Complexity of Uniform Membership of Context-Free Tree Grammars"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Osterholzer","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,9]]},"reference":[{"issue":"4","key":"16_CR1","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\u2013an extension of context-free grammars. J. ACM 15(4), 647\u2013671 (1968)","journal-title":"J. ACM"},{"issue":"1","key":"16_CR2","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1080\/00207168108803261","volume":"10","author":"P Asveld","year":"1981","unstructured":"Asveld, P.: Time and space complexity of inside-out macro languages. Int. J. Comput. Math. 10(1), 3\u201314 (1981)","journal-title":"Int. J. Comput. Math."},{"key":"16_CR3","unstructured":"Engelfriet, J., Schmidt, E.M.: IO and OI. J. Comput. Syst. Sci. 15(3), 328\u2013353 (1977); and 16(1), 67\u201399 (1978)"},{"key":"16_CR4","unstructured":"Guessarian, I.: Pushdown tree automata. Math. Syst. Theory 16(1), 237\u2013263 (1983)"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"Kozen, D.: Lower bounds for natural proof systems. In: Proc. 18th Symp. Foundations of Computer Science, pp. 254\u2013266 (1977)","DOI":"10.1109\/SFCS.1977.16"},{"key":"16_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/3-540-45127-7_16","volume-title":"Rewriting Techniques and Applications","author":"M Lohrey","year":"2001","unstructured":"Lohrey, M.: On the parallel complexity of tree automata. In: Middeldorp, A. (ed.) RTA 2001. LNCS, vol. 2051, p. 201. Springer, Heidelberg (2001)"},{"key":"16_CR7","unstructured":"Inaba, K., Maneth, S.: The complexity of tree transducer output languages. In: Proc. of FSTTCS 2008, pp. 244\u2013255 (2008)"},{"key":"16_CR8","unstructured":"Papadimitriou, C.H.: Computational Complexity. John Wiley and Sons (2003)"},{"issue":"3","key":"16_CR9","first-page":"257","volume":"4","author":"WC Rounds","year":"1970","unstructured":"Rounds, W.C.: Mappings and grammars on trees. Theor. Comput. Syst. 4(3), 257\u2013287 (1970)","journal-title":"Theor. Comput. Syst."},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Rounds, W.C.: Tree-oriented proofs of some theorems on context-free and indexed languages. In: Proc. 2nd ACM Symp. Theory of Comput., pp. 109\u2013116 (1970)","DOI":"10.1145\/800161.805156"},{"key":"16_CR11","doi-asserted-by":"crossref","unstructured":"Rounds, W.C.: Complexity of recognition in intermediate level languages. In: Proc. 14th Symp. Switching and Automata Theory, pp. 145\u2013158 (1973)","DOI":"10.1109\/SWAT.1973.5"},{"issue":"2","key":"16_CR12","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"9","key":"16_CR13","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/scj.4690170904","volume":"17","author":"S Tanaka","year":"1986","unstructured":"Tanaka, S., Kasai, T.: The emptiness problem for indexed language is exponential-time complete. Syst. Comput. Jpn. 17(9), 29\u201337 (1986)","journal-title":"Syst. Comput. Jpn."},{"key":"16_CR14","unstructured":"Yoshinaka, R.: An attempt towards learning semantics: Distributional learning of IO context-free tree grammars. In: Proc. of TAG+11, pp. 90\u201398 (2012)"}],"container-title":["Lecture Notes in Computer Science","Algebraic Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23021-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T18:30:06Z","timestamp":1559241006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-23021-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319230207","9783319230214"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23021-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}