{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:49:31Z","timestamp":1725475771901},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540677789"},{"type":"electronic","value":"9783540449805"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/10721975_12","type":"book-chapter","created":{"date-parts":[[2006,12,29]],"date-time":"2006-12-29T20:43:04Z","timestamp":1167424984000},"page":"172-186","source":"Crossref","is-referenced-by-count":2,"title":["Word Problems and Confluence Problems for Restricted Semi-Thue Systems"],"prefix":"10.1007","author":[{"given":"Markus","family":"Lohrey","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"12_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/3-540-10856-4_87","volume-title":"Mathematical Foundations of Computer Science 1981","author":"R. Book","year":"1981","unstructured":"Book, R., Jantzen, M., Monien, B., O\u2019Dunlaing, C.P., Wrathall, C.: On the complexity of word problems in certain Thue systems. In: Gruska, J., Chytil, M.P. (eds.) MFCS 1981. LNCS, vol.\u00a0118, pp. 216\u2013223. Springer, Heidelberg (1981)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-55719-9_65","volume-title":"Automata, Languages and Programming","author":"G. Buntrock","year":"1992","unstructured":"Buntrock, G., Lory\u015b, K.: On growing context-sensitive languages. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol.\u00a0623, pp. 77\u201388. Springer, Heidelberg (1992)"},{"key":"12_CR3","series-title":"Lecture Notes in Computer Science","first-page":"595","volume-title":"STACS 94","author":"G. Buntrock","year":"1994","unstructured":"Buntrock, G., Lory\u015b, K.: The variable membership problem: Succinctness versus complexity. In: Enjalbert, P., Mayr, E.W., Wagner, K.W. (eds.) STACS 1994. LNCS, vol.\u00a0775, pp. 595\u2013606. Springer, Heidelberg (1994)"},{"key":"12_CR4","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(81)90078-5","volume":"16","author":"R.V. Book","year":"1981","unstructured":"Book, R.V., O\u2019Dunlaing, C.P.: Testing for the Church-Rosser property (note). Theoretical Computer Science\u00a016, 223\u2013229 (1981)","journal-title":"Theoretical Computer Science"},{"key":"12_CR5","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/BF00271645","volume":"21","author":"G. Bauer","year":"1984","unstructured":"Bauer, G., Otto, F.: Finite complete rewriting systems and the complexity of the word problem. Acta Informatica\u00a021, 521\u2013540 (1984)","journal-title":"Acta Informatica"},{"key":"12_CR6","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-9771-7","volume-title":"String-Rewriting Systems","author":"R.V. Book","year":"1993","unstructured":"Book, R.V., Otto, F.: String-Rewriting Systems. Springer, Heidelberg (1993)"},{"issue":"1","key":"12_CR7","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1145\/322290.322301","volume":"29","author":"R.V. Book","year":"1982","unstructured":"Book, R.V.: Confluent and other types of Thue systems. Journal of the Association for Computing Machinery\u00a029(1), 171\u2013182 (1982)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR8","unstructured":"Cardoza, E.W.: Computational complexity of the word problem for commutative semigroups. Technical Report MAC Technical Memorandum 67, MIT (1975)"},{"key":"12_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1080\/00207169008803946","volume":"37","author":"S. Cho","year":"1990","unstructured":"Cho, S., Huynh, D.T.: The complexity of membership for deterministic growing context-sensitive grammars. International Journal of Computer Mathematics\u00a037, 185\u2013188 (1990)","journal-title":"International Journal of Computer Mathematics"},{"key":"12_CR10","unstructured":"Diekert, V.: Some properties of weight-reducing presentations. Report TUM-I8710, Technical University Munich (1987)"},{"key":"12_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-53031-2","volume-title":"Combinatorics on Traces","author":"V. Diekert","year":"1990","unstructured":"Diekert, V.: Combinatorics on Traces. LNCS, vol.\u00a0454. Springer, Heidelberg (1990)"},{"key":"12_CR12","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/0022-0000(86)90062-0","volume":"33","author":"E. Dahlhaus","year":"1986","unstructured":"Dahlhaus, E., Warmuth, M.K.: Membership for growing contextsensitive grammars is polynomial. Journal of Computer and System Sciences\u00a033, 456\u2013472 (1986)","journal-title":"Journal of Computer and System Sciences"},{"key":"12_CR13","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0304-3975(84)90092-6","volume":"33","author":"D.T. Huynh","year":"1984","unstructured":"Huynh, D.T.: Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is $\\Sigma^{p}_{2}$ -complete. Theoretical Computer Science\u00a033, 305\u2013326 (1984)","journal-title":"Theoretical Computer Science"},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/BF00288776","volume":"22","author":"D.T. Huynh","year":"1985","unstructured":"Huynh, D.T.: Complexity of the word problem for commutative semigroups of fixed dimension. Acta Informatica\u00a022, 421\u2013432 (1985)","journal-title":"Acta Informatica"},{"issue":"2","key":"12_CR15","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1137\/0215042","volume":"15","author":"D.T. Huynh","year":"1986","unstructured":"Huynh, D.T.: The complexity of the membership problem for two subclasses of polynomial ideals. SIAM Journal on Computing\u00a015(2), 581\u2013594 (1986)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR16","series-title":"EATCS Monographs on theoretical computer science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61549-8","volume-title":"Confluent string rewriting","author":"M. Jantzen","year":"1988","unstructured":"Jantzen, M.: Confluent string rewriting. EATCS Monographs on theoretical computer science, vol.\u00a014. Springer, Heidelberg (1988)"},{"key":"12_CR17","first-page":"263","volume-title":"Computational Problems in Abstact Algebras","author":"D.E. Knuth","year":"1967","unstructured":"Knuth, D.E., Bendix, P.B.: Simple Word Problems in Universal Algebras. In: Leech, J. (ed.) Computational Problems in Abstact Algebras, pp. 263\u2013297. Pergamon Press, Elmsford N.Y (1967)"},{"issue":"1","key":"12_CR18","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0304-3975(85)90008-8","volume":"35","author":"D. Kapur","year":"1985","unstructured":"Kapur, D., Krishnamoorthy, M.S., McNaughton, R., Narendran, P.: An O(|T|3) algorithm for testing the Church-Rosser property of Thue systems. Theoretical Computer Science\u00a035(1), 109\u2013114 (1985)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"12_CR19","doi-asserted-by":"publisher","first-page":"1052","DOI":"10.1137\/0214073","volume":"14","author":"D. Kapur","year":"1985","unstructured":"Kapur, D., Narendran, P.: The Knuth-Bendix completion procedure and Thue systems. SIAM Journal on Computing\u00a014(3), 1052\u20131072 (1985)","journal-title":"SIAM Journal on Computing"},{"key":"12_CR20","unstructured":"Krithivasan, K., Narendran, P.: On the membership problem for some grammars. Technical Report CS-TR-1787, University of Maryland (1987)"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1007\/3-540-48340-3_11","volume-title":"Mathematical Foundations of Computer Science 1999","author":"M. Lohrey","year":"1999","unstructured":"Lohrey, M.: Complexity results for confluence problems. In: Kuty\u0142owski, M., Wierzbicki, T., Pacholski, L. (eds.) MFCS 1999. LNCS, vol.\u00a01672, pp. 114\u2013124. Springer, Heidelberg (1999)"},{"key":"12_CR22","first-page":"587","volume":"55, 58","author":"A. Markov","year":"1947","unstructured":"Markov, A.: On the impossibility of certain algorithms in the theory of associative systems. Doklady Akademii Nauk SSSR\u00a055, 58, 587\u2013590, 353\u2013356 (1947)","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/0001-8708(82)90048-2","volume":"46","author":"E.W. Mayr","year":"1982","unstructured":"Mayr, E.W., Meyer, A.R.: The complexity of the word problems for commutative semigroups and polynomial ideals. Advances in Mathematics\u00a046, 305\u2013329 (1982)","journal-title":"Advances in Mathematics"},{"issue":"2","key":"12_CR24","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/42282.42284","volume":"35","author":"R. McNaughton","year":"1988","unstructured":"McNaughton, R., Narendran, P., Otto, F.: Church-Rosser Thue systems and formal languages. Journal of the Association for Computing Machinery\u00a035(2), 324\u2013344 (1988)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR25","unstructured":"Nivat, M., Benois, M.: Congruences parfaites et quasi-parfaites. Seminaire Dubreil, 25(7-01-09) (1971\u20131972)"},{"key":"12_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.2307\/1968867","volume":"43","author":"M.H.A. Newman","year":"1943","unstructured":"Newman, M.H.A.: On theories with a combinatorial definition of \u201cequivalence\u201d. Annals Mathematics\u00a043, 223\u2013243 (1943)","journal-title":"Annals Mathematics"},{"key":"12_CR27","doi-asserted-by":"crossref","first-page":"573","DOI":"10.1007\/BF00279954","volume":"25","author":"P. Narendran","year":"1988","unstructured":"Narendran, P., Otto, F.: Elements of finite order for finite weigthreducing and confluent Thue systems. Acta Informatica\u00a025, 573\u2013591 (1988)","journal-title":"Acta Informatica"},{"key":"12_CR28","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison Wesley, Reading (1994)"},{"issue":"1","key":"12_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2307\/2267170","volume":"12","author":"E. Post","year":"1947","unstructured":"Post, E.: Recursive unsolvability of a problem of Thue. Journal of Symbolic Logic\u00a012(1), 1\u201311 (1947)","journal-title":"Journal of Symbolic Logic"},{"issue":"3","key":"12_CR30","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I.H. Sudborough","year":"1978","unstructured":"Sudborough, I.H.: On the tape complexity of deterministic context- free languages. Journal of the Association for Computing Machinery\u00a025(3), 405\u2013414 (1978)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/BFb0052369","volume-title":"Rewriting Techniques and Applications","author":"R.M. Verma","year":"1998","unstructured":"Verma, R.M., Rusinowitch, M., Lugiez, D.: Algorithms and reductions for rewriting problems. In: Nipkow, T. (ed.) RTA 1998. LNCS, vol.\u00a01379, pp. 166\u2013180. Springer, Heidelberg (1998)"},{"issue":"1","key":"12_CR32","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1090\/S0002-9939-1978-0500555-0","volume":"72","author":"J. Zur Gathen von","year":"1978","unstructured":"von Zur Gathen, J., Sieveking, M.: A bound on solutions of linear integer equalities and inequalities. Proceedings of the American Mathematical Society\u00a072(1), 155\u2013158 (1978)","journal-title":"Proceedings of the American Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","Rewriting Techniques and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/10721975_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,9]],"date-time":"2024-02-09T17:36:34Z","timestamp":1707500194000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/10721975_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677789","9783540449805"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/10721975_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2000]]}}}