{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:57Z","timestamp":1725490257000},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_44","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T21:32:38Z","timestamp":1188336758000},"page":"500-512","source":"Crossref","is-referenced-by-count":3,"title":["Word Problems for 2-Homogeneous Monoids and Symmetric Logspace"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"44_CR1","unstructured":"S.I. Adjan. Defining relations and algorithmic problems for groups and semigroups, volume 85 of Proceedings of the Steklov Institute of Mathematics. American Mathematical Society, 1967."},{"key":"44_CR2","unstructured":"C. Alvarez and R. Greenlaw. A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity, Report No. TR96-039, 1996."},{"issue":"2","key":"44_CR3","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/333979.333984","volume":"47","author":"R. Armoni","year":"2000","unstructured":"R. Armoni, A. Ta-Shma, A. Widgerson, and S. Zhou. An O(log(n)4\/3) space algorithm for (s, t) connectivity in undirected graphs. Journal of the Association for Computing Machinery, 47(2):294\u2013311, 2000.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"44_CR4","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":"44_CR5","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"},{"key":"44_CR6","doi-asserted-by":"crossref","unstructured":"R. Book and F. Otto. String-Rewriting Systems. Springer, 1993.","DOI":"10.1007\/978-1-4613-9771-7"},{"issue":"1","key":"44_CR7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R. V. Book","year":"1982","unstructured":"R. V. Book. Confluent and other types of Thue systems. Journal of the Association for Computing Machinery, 29(1):171\u2013182, 1982.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"44_CR8","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/0012-365X(84)90177-8","volume":"48","author":"R. V. Book","year":"1984","unstructured":"R. V. Book. Homogeneous Thue systems and the Church-Rosser property. Discrete Mathematics, 48:137\u2013145, 1984.","journal-title":"Discrete Mathematics"},{"key":"44_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-10856-4_87","volume-title":"Proceedings of the 10rd Mathematical Foundations of Computer Science (MFCS\u201981), Strbsk\u00e9 Pleso (Czechoslovakia)","author":"R. V. Book","year":"1981","unstructured":"R. V. Book, M. Jantzen, B. Monien, C. P. O\u2019Dunlaing, and C. Wrathall. On the complexity of word problems in certain Thue systems. In J. Gruska and M. Chytil, editors, Proceedings of the 10rd Mathematical Foundations of Computer Science (MFCS\u201981), Strbsk\u00e9 Pleso (Czechoslovakia), number 118 in Lecture Notes in Computer Science, pages 216\u2013223. Springer, 1981."},{"key":"44_CR10","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":"44_CR11","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"issue":"4","key":"44_CR12","doi-asserted-by":"publisher","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(4):760\u2013778, 1987.","journal-title":"SIAM Journal on Computing"},{"key":"44_CR13","doi-asserted-by":"crossref","unstructured":"M. Jantzen. Confluent string rewriting. In EATCS Monographs on theoretical computer science, volume 14. Springer, 1988.","DOI":"10.1007\/978-3-642-61549-8"},{"issue":"2","key":"44_CR14","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H. R. Lewis","year":"1982","unstructured":"H. R. Lewis and C. H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science, 19(2):161\u2013187, 1982.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"44_CR15","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. Journal of the Association for Computing Machinery, 24(3):522\u2013526, 1977.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"44_CR16","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/10721975_12","volume-title":"Proceedings of the 11th International Conference on Rewrite Techniques and Applications (RTA 2000), Norwich (UK)","author":"M. Lohrey","year":"2000","unstructured":"M. Lohrey. Word problems and confluence problems for restricted semi-Thue systems. In L. Bachmair, editor, Proceedings of the 11th International Conference on Rewrite Techniques and Applications (RTA 2000), Norwich (UK), number 1833 in Lecture Notes in Computer Science, pages 172\u2013186. Springer, 2000."},{"key":"44_CR17","unstructured":"R. C. Lyndon and P. E. Schupp. Combinatorial Group Theory. Springer, 1977."},{"issue":"58","key":"44_CR18","first-page":"587","volume":"55","author":"A. Markov","year":"1947","unstructured":"A. Markov. On the impossibility of certain algorithms in the theory of associative systems. Doklady Akademii Nauk SSSR, 55,58:587\u2013590, 353\u2013356, 1947.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"44_CR19","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ta-Shma. Symmetric logspace is closed under complement. Chicago Journal of Theoretical Computer Science, 1995.","DOI":"10.4086\/cjtcs.1995.001"},{"key":"44_CR20","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/BF01178585","volume":"28","author":"F. Otto","year":"1991","unstructured":"F. Otto and L. Zhang. Decision problems for finite special string-rewriting systems that are confluent on some congruence class. Acta Informatica, 28:477\u2013510, 1991.","journal-title":"Acta Informatica"},{"key":"44_CR21","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison Wesley, 1994."},{"issue":"1","key":"44_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. Post","year":"1947","unstructured":"E. Post. Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic, 12(1):1\u201311, 1947.","journal-title":"Journal of Symbolic Logic"},{"key":"44_CR23","series-title":"PhD thesis","volume-title":"Parallel Algorithms for Group Word Problems","author":"D. Robinson","year":"1993","unstructured":"D. Robinson. Parallel Algorithms for Group Word Problems. PhD thesis, University of California, San Diego, 1993."},{"key":"44_CR24","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"},{"key":"44_CR25","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0020-0190(91)90121-W","volume":"40","author":"I. Stewart","year":"1991","unstructured":"I. Stewart. Complete problems for symmetric logspace involving free groups. Information Processing Letters, 40:263\u2013267, 1991.","journal-title":"Information Processing Letters"},{"key":"44_CR26","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1142\/S0218196792000141","volume":"2","author":"I. Stewart","year":"1992","unstructured":"I. Stewart. Refining known results on the generalized word problem for free groups. International Journal of Algebra and Computation, 2:221\u2013236, 1992.","journal-title":"International Journal of Algebra and Computation"},{"key":"44_CR27","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","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T01:49:01Z","timestamp":1550886541000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_44","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}