{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:59Z","timestamp":1759638599687},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540633853"},{"type":"electronic","value":"9783540698067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63385-5_30","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:26:27Z","timestamp":1330298787000},"page":"18-33","source":"Crossref","is-referenced-by-count":33,"title":["Alogtime algorithms for tree isomorphism, comparison, and canonization"],"prefix":"10.1007","author":[{"given":"Samuel R.","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,8]]},"reference":[{"key":"3_CR1","unstructured":"A. V. AHO, J. E. HOPCROFT, AND J. D. ULLMAN, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974."},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1016\/0022-0000(89)90037-8","volume":"38","author":"D. A. M. Barrington","year":"1989","unstructured":"D. A. M. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, J. Comput. System Sci., 38 (1989), pp. 150\u2013164.","journal-title":"J. Comput. System Sci."},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"S. R. Buss, The Boolean formula value problem is in ALOGTIME, in Proceedings of the 19-th Annual ACM Symposium on Theory of Computing, May 1987, pp. 123\u2013131.","DOI":"10.1145\/28395.28409"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"\u2014, Algorithms for Boolean formula evaluation and for tree contraction, in Arithmetic, Proof Theory and Computational Complexity, P. Clote and J. Kraj\u00ed\u010dek, eds., Oxford University Press, 1993, pp. 96\u2013115.","DOI":"10.1093\/oso\/9780198536901.003.0005"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. R. Buss","year":"1992","unstructured":"S. R. Buss, S. A. Cook, A. Gupta, and V. Ramachandran, An optimal parallel algorithm for formula evaluation, SIAM J. Comput., 21 (1992), pp. 755\u2013780.","journal-title":"SIAM J. Comput."},{"key":"3_CR6","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0166-218X(90)90081-M","volume":"29","author":"P. B. Gibbons","year":"1990","unstructured":"P. B. Gibbons, R. M. Karp, G. L. Miller, and D. Soroker, Subtree isomorphism in in random NC, Discrete Applied Mathematics, 29 (1990), pp. 35\u201362.","journal-title":"Discrete Applied Mathematics"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"760","DOI":"10.1137\/0216051","volume":"16","author":"N. Immerman","year":"1987","unstructured":"N. Immerman, Languages that capture complexity classes, SIAM Journal on Computing, 16 (1987), pp. 760\u2013778.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"S. LINDELL, A logspace algorithm for tree canonization, in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992, pp. 400\u2013404.","DOI":"10.1145\/129712.129750"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0020-0190(89)90170-1","volume":"30","author":"A. Lingas","year":"1989","unstructured":"A. Lingas and M. Karpinski, Subtree isomorphism is NC reducible to bipartite perfect matching, Information Processing Letters, 30 (1989), pp. 27\u201332.","journal-title":"Information Processing Letters"},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1145\/322017.322031","volume":"24","author":"R. J. Lipton","year":"1977","unstructured":"R. J. Lipton and Y. Zalcstein, Word problems solvable in logspace, J. Assoc. Comput. Mach., 24 (1977), pp. 522\u2013526.","journal-title":"J. Assoc. Comput. Mach."},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1016\/S0167-5060(08)70324-8","volume":"2","author":"D. W. Matula","year":"1978","unstructured":"D. W. Matula, Subtree isomorphism in O(n5\/2), Annals of Discrete Mathematics, 2 (1978), pp. 91\u2013106.","journal-title":"Annals of Discrete Mathematics"},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"1128","DOI":"10.1137\/0220070","volume":"20","author":"G. L. Miller","year":"1991","unstructured":"G. L. Miller and J. H.Reif, Parallel tree contraction part 2: Further applications, SIAM Journal on Computing, 20 (1991), pp. 1128\u20131147.","journal-title":"SIAM Journal on Computing"},{"key":"3_CR13","doi-asserted-by":"crossref","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, J. Comput. System Sci., 22 (1981), pp. 365\u2013383.","journal-title":"J. Comput. System Sci."}],"container-title":["Lecture Notes in Computer Science","Computational Logic and Proof Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63385-5_30.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T18:13:12Z","timestamp":1713636792000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63385-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540633853","9783540698067"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/3-540-63385-5_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}