{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T14:04:28Z","timestamp":1725545068185},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540310235"},{"type":"electronic","value":"9783540330974"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11605157_19","type":"book-chapter","created":{"date-parts":[[2006,3,1]],"date-time":"2006-03-01T10:07:40Z","timestamp":1141207660000},"page":"225-237","source":"Crossref","is-referenced-by-count":5,"title":["Tree Automata and XPath on Compressed Trees"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sebastian","family":"Maneth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"906","DOI":"10.1007\/978-3-540-27836-8_76","volume-title":"Automata, Languages and Programming","author":"M. Lohrey","year":"2004","unstructured":"Lohrey, M.: Word problems on compressed word. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 906\u2013918. Springer, Heidelberg (2004)"},{"key":"19_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-540-27836-8_5","volume-title":"Automata, Languages and Programming","author":"W. Rytter","year":"2004","unstructured":"Rytter, W.: Grammar compression, LZ-encodings, and string algorithms with implicit input. In: D\u00edaz, J., Karhum\u00e4ki, J., Lepist\u00f6, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol.\u00a03142, pp. 15\u201327. Springer, Heidelberg (2004)"},{"key":"19_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1142\/9789812815149_0001","volume-title":"Handbook of Graph Grammars and Computing by Graph Transformation","author":"D. Plump","year":"1999","unstructured":"Plump, D.: Term graph rewriting. In: Ehrig, H., Engels, G., Kreowski, H.J., Rozenberg, G. (eds.) Handbook of Graph Grammars and Computing by Graph Transformation, vol.\u00a02, pp. 3\u201361. World Scientific, Singapore (1999)"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R.E. Bryant","year":"1992","unstructured":"Bryant, R.E.: Symbolic boolean manipulation with ordered binary-decision diagrams. ACM Computing Surveys\u00a024, 293\u2013318 (1992)","journal-title":"ACM Computing Surveys"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1016\/B978-012722442-8\/50021-5","volume-title":"Proc.\u00a0VLDB 2003","author":"P. Buneman","year":"2003","unstructured":"Buneman, P., Grohe, M., Koch, C.: Path queries on compressed XML. In: Freytag, J.C., et al. (eds.) Proc.\u00a0VLDB 2003, pp. 141\u2013152. Morgan Kaufmann, San Francisco (2003)"},{"key":"19_CR6","first-page":"188","volume-title":"Proc.\u00a0LICS 2003","author":"M. Frick","year":"2003","unstructured":"Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: Proc.\u00a0LICS 2003, pp. 188\u2013197. IEEE Computer Society Press, Los Alamitos (2003)"},{"key":"19_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-540-24727-2_26","volume-title":"Foundations of Software Science and Computation Structures","author":"S. Maneth","year":"2004","unstructured":"Maneth, S., Busatto, G.: Tree transducers and tree compressions. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol.\u00a02987, pp. 363\u2013377. Springer, Heidelberg (2004)"},{"key":"19_CR8","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree automata techniques and applications (2002), available on: \n                    \n                      http:\/\/www.grappa.univ-lille3.fr\/tata"},{"key":"19_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_13","volume-title":"Database Programming Languages","author":"G. Busatto","year":"2005","unstructured":"Busatto, G., Lohrey, M., Maneth, S.: Efficient memory representation of XML documents. In: Bierman, G., Koch, C. (eds.) DBPL 2005. LNCS, vol.\u00a03774, Springer, Heidelberg (2005)"},{"key":"19_CR10","unstructured":"G\u00e9cseg, F., Steinby, M.: Tree automata. Akad\u00e9miai Kiad\u00f3 (1984)"},{"key":"19_CR11","unstructured":"Murata, M., Lee, D., Mani, M.: Taxonomy of XML Schema Languages using Formal Language Theory. In: Proc.\u00a0Extreme Markup Languages 2000, Montr\u00e9al (Canada) (2000)"},{"key":"19_CR12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F. Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Record\u00a031, 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"key":"19_CR13","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.\u00a02051, pp. 201\u2013215. Springer, Heidelberg (2001)"},{"key":"19_CR14","first-page":"167","volume-title":"Proc.\u00a0PODS 2003","author":"L. Segoufin","year":"2003","unstructured":"Segoufin, L.: Typing and querying XML documents: some complexity bounds. In: Proc.\u00a0PODS 2003, pp. 167\u2013178. ACM Press, New York (2003)"},{"key":"19_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parametrized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parametrized Complexity. Springer, Heidelberg (1999)"},{"key":"19_CR16","first-page":"95","volume-title":"Proc.\u00a0VLDB 2002","author":"G. Gottlob","year":"2002","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. In: Proc.\u00a0VLDB 2002, pp. 95\u2013106. Morgan Kaufmann, San Francisco (2002)"},{"key":"19_CR17","first-page":"179","volume-title":"Proc.\u00a0PODS 2003","author":"G. Gottlob","year":"2003","unstructured":"Gottlob, G., Koch, C., Pichler, R.: The complexity of XPath query evaluation. In: Proc.\u00a0PODS 2003, pp. 179\u2013190. ACM Press, New York (2003)"},{"key":"19_CR18","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"19_CR19","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139172752","volume-title":"Term Rewriting and All That","author":"F. Baader","year":"1998","unstructured":"Baader, F., Nipkow, T.: Term Rewriting and All That. Cambridge University Press, Cambridge (1998)"},{"key":"19_CR20","doi-asserted-by":"publisher","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. Theoretical Computer Science\u00a06, 255\u2013279 (1978)","journal-title":"Theoretical Computer Science"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/j.ipl.2005.02.004","volume":"94","author":"S. Anantharaman","year":"2005","unstructured":"Anantharaman, S., Narendran, P., Rusinowitch, M.: Closure properties and decision problems of dag automata. Information Processing Letters\u00a094, 231\u2013240 (2005)","journal-title":"Information Processing Letters"},{"key":"19_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.ipl.2004.01.002","volume":"90","author":"N. Markey","year":"2004","unstructured":"Markey, N., Schnoebelen, P.: A PTIME-complete matching problem for SLP-compressed words. Information Processing Letters\u00a090, 3\u20136 (2004)","journal-title":"Information Processing Letters"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1006\/jcss.1999.1626","volume":"58","author":"C.H. Papadimitriou","year":"1999","unstructured":"Papadimitriou, C.H., Yannakakis, M.: On the complexity of database queries. Journal of Computer and System Sciences\u00a058, 407\u2013427 (1999)","journal-title":"Journal of Computer and System Sciences"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11605157_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T03:05:15Z","timestamp":1619492715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11605157_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540310235","9783540330974"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/11605157_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}