{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:53:29Z","timestamp":1759683209303,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540421177"},{"type":"electronic","value":"9783540451273"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-45127-7_16","type":"book-chapter","created":{"date-parts":[[2007,7,16]],"date-time":"2007-07-16T16:25:25Z","timestamp":1184603125000},"page":"201-215","source":"Crossref","is-referenced-by-count":15,"title":["On the Parallel Complexity of Tree Automata"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,5,8]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0020-0190(89)90052-5","volume":"32","author":"D. A. M. Barrington","year":"1989","unstructured":"D. A. M. Barrington and J. Corbet. On the relative complexity of some languages in NC1. Information Processing Letters, 32:251\u2013256, 1989.","journal-title":"Information Processing Letters"},{"key":"16_CR2","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1016\/0022-0000(90)90022-D","volume":"41","author":"D. A. M. Barrington","year":"1990","unstructured":"D. A. M. Barrington, N. Immerman, and H. Straubing. On uniformity within NC1. Journal of Computer and System Sciences, 41:274\u2013306, 1990.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"16_CR3","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1006\/jcss.1995.1035","volume":"50","author":"M. Beaudry","year":"1995","unstructured":"M. Beaudry and P. McKenzie. Circuits, matrices, and nonassociative computation. Journal of Computer and System Sciences, 50(3):441\u2013455, 1995.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR4","doi-asserted-by":"crossref","unstructured":"J. Berman, A. Drisko, F. Lemieux, C. Moore, and D. Th\u00e9rien. Circuits and expressions with non-associative gates. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity, Ulm (Germany), pages 193\u2013203. IEEE Computer Society Press, 1997.","DOI":"10.1109\/CCC.1997.612315"},{"key":"16_CR5","doi-asserted-by":"crossref","unstructured":"S. R. Buss. The Boolean formula value problem is in ALOGTIME. In Proceedings of the 19th Annual Symposium on Theory of Computing (STOC 87), pages 123\u2013131. ACM Press, 1987.","DOI":"10.1145\/28395.28409"},{"key":"16_CR6","doi-asserted-by":"crossref","unstructured":"S. R. Buss. Alogtime algorithms for tree isomorphism, comparison, and canonization. In Kurt G\u00f6del Colloquium 97, pages 18\u201333, 1997.","DOI":"10.1007\/3-540-63385-5_30"},{"key":"16_CR7","unstructured":"H. Comon, M. Dauchet, R. Gilleron, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree automata techniques and applications. Available on: http:\/\/www.grappa.univ-lille3.fr\/tata , 1997."},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-6774(87)90018-6","volume":"8","author":"S. A. Cook","year":"1987","unstructured":"S. A. Cook and P. McKenzie. Problems complete for deterministic logarithmic space. Journal of Algorithms, 8:385\u2013394, 1987.","journal-title":"Journal of Algorithms"},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"M. Dauchet and S. Tison. The theory of ground rewrite systems is decidable. In Proceedings of the 5th Annual IEEE Symposium on Logic in Computer Science (LICS\u2019 90), pages 242\u2013256. IEEE Computer Society Press, 1990.","DOI":"10.1109\/LICS.1990.113750"},{"key":"16_CR10","first-page":"243","volume-title":"Handbook of Theoretical Computer Science","author":"N. Dershowitz","year":"1990","unstructured":"N. Dershowitz and J.-P. Jouannaud. Rewriting systems. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, pages 243\u2013320. Elsevier Publishers, Amsterdam, 1990."},{"key":"16_CR11","first-page":"365","volume":"12","author":"J. E. Doner","year":"1965","unstructured":"J. E. Doner. Decidability of the weak second-order theory of two successors. Notices Amer. Math. Soc., 12:365\u2013468, 1965.","journal-title":"Notices Amer. Math. Soc."},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/S0022-0000(70)80041-1","volume":"4","author":"J. E. Doner","year":"1970","unstructured":"J. E. Doner. Tree acceptors and some of their applications. Journal of Computer and System Sciences, 4:406\u2013451, 1970.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR13","doi-asserted-by":"crossref","unstructured":"J. Engelfriet and H. J. Hoogeboom. Tree-walking pebble automata. In J. Karhum\u00e4ki, H. Maurer, G. Paun, and G. Rozenberg, editors, Jewels are Forever, Contributions on Theoretical Computer Science in Honor of Arto Salomaa, pages 72\u201383. Springer, 1999.","DOI":"10.1007\/978-3-642-60207-8_7"},{"key":"16_CR14","unstructured":"F. G\u00e9cseg and M. Steinby. Tree automata. Akad\u00e9miai Kiad\u00f3, 1984."},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"G. Gottlob, N. Leone, and F. Scarcello. The complexity of acyclic conjunctive queries. In Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS 98, Palo Alto, California, USA), pages 706\u2013715. IEEE Computer Society Press, 1998.","DOI":"10.1109\/SFCS.1998.743521"},{"issue":"4","key":"16_CR16","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1137\/0202025","volume":"2","author":"S. Greibach","year":"1973","unstructured":"S. Greibach. The hardest context-free language. SIAM Journal on Computing, 2(4):304\u2013310, 1973.","journal-title":"SIAM Journal on Computing"},{"key":"16_CR17","unstructured":"M. A. Harrison. Introduction to Formal Language Theory. Addison-Wesley, 1978."},{"key":"16_CR18","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/3-540-57163-9_25","volume-title":"Proceedings of the 9th International Symposium on Fundamentals of Computation Theory (FCT\u201993, Szeged, Hungary)","author":"M. Holzer","year":"1993","unstructured":"M. Holzer and K.-J. Lange. On the complexities of linear LL(1) and LR(1) grammars. In Z. \u00c9sik, editor, Proceedings of the 9th International Symposium on Fundamentals of Computation Theory (FCT\u201993, Szeged, Hungary), number 710 in Lecture Notes in Computer Science, pages 299\u2013308. Springer, 1993."},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"B. Jenner, P. McKenzie, and J. Tor\u00e1n. A note on the hardness of tree isomorphism. In Proceedings of the 13th Annual IEEE Conference on Computational Complexity, pages 101\u2013105. IEEE Computer Society Press, 1998.","DOI":"10.1109\/CCC.1998.694595"},{"issue":"1","key":"16_CR20","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N. D. Jones. Space-bounded reducibility among combinatorial problems. Journal of Computer and System Sciences, 11(1):68\u201385, 1975.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR21","doi-asserted-by":"crossref","unstructured":"D. C. Kozen. Complexity of finitely presented algebras. In 9th Annual Symposium on Theory of Computing (STOC 77), pages 164\u2013177. ACM Press, 1977.","DOI":"10.1145\/800105.803406"},{"issue":"3","key":"16_CR22","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R. McNaughton","year":"1967","unstructured":"R. McNaughton. Parenthesis grammars. Journal of the Association for Computing Machinery, 14(3):490\u2013500, 1967.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"16_CR23","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994."},{"key":"16_CR24","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. L. Ruzzo","year":"1980","unstructured":"W. L. Ruzzo. Tree-size bounded alternation. Journal of Computer and System Sciences, 21:218\u2013235, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. L. Ruzzo","year":"1981","unstructured":"W. L. Ruzzo. On uniform circuit complexity. Journal of Computer and System Sciences, 22:365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"16_CR26","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. H. Sudborough","year":"1978","unstructured":"I. H. Sudborough. On the tape complexity of deterministic context-free languages. Journal of the Association for Computing Machinery, 25(3):405\u2013414, 1978.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"16_CR27","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J. W. Thatcher","year":"1968","unstructured":"J. W. Thatcher and J. B. Wright. Generalized finite automata with an application to a decision problem of second order logic. Mathematical Systems Theory, 2:57\u201382, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"16_CR28","unstructured":"M. Veanes. On computational complexity of basic decision problems of finite tree automata. Technical Report 133, Uppsala Computing Science Department, 1997."},{"key":"16_CR29","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/0022-0000(91)90020-6","volume":"43","author":"H. Venkateswaran","year":"1991","unstructured":"H. Venkateswaran. Properties that characterize LOGCFL. Journal of Computer and System Sciences, 43:380\u2013404, 1991.","journal-title":"Journal of Computer and System Sciences"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"H. Vollmer. Introduction to Circuit Complexity. Springer, 1999.","DOI":"10.1007\/978-3-662-03927-4"}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45127-7_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,19]],"date-time":"2025-01-19T11:58:10Z","timestamp":1737287890000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45127-7_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540421177","9783540451273"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/3-540-45127-7_16","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}