{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T21:04:13Z","timestamp":1776200653621,"version":"3.50.1"},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1991,5,1]],"date-time":"1991-05-01T00:00:00Z","timestamp":673056000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[1991,5]]},"DOI":"10.1007\/bf01178585","type":"journal-article","created":{"date-parts":[[2005,2,17]],"date-time":"2005-02-17T19:55:25Z","timestamp":1108670125000},"page":"477-510","source":"Crossref","is-referenced-by-count":18,"title":["Decision problems for finite special string-rewriting systems that are confluent on some congruence class"],"prefix":"10.1007","volume":"28","author":[{"given":"Friedrich","family":"Otto","sequence":"first","affiliation":[]},{"given":"Louxin","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"#cr-split#-CR1.1","unstructured":"Adjan, S.: Defining relations and algorithmic problems for groups and semigroups. Proc. Steklov Inst. Math.85 (1966);"},{"key":"#cr-split#-CR1.2","unstructured":"English version: Am. Math. Soc. Transl.152 (1967)"},{"key":"CR2","series-title":"Lect. Notes Comput. Sci.","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-18598-4","volume-title":"Systems of reductions","author":"B. Benninghofen","year":"1987","unstructured":"Benninghofen, B., Kemmerich, S., Richter, M.M.: Systems of reductions. (Lect. Notes Comput. Sci., vol. 277). Berlin Heidelberg New York: Springer 1987"},{"key":"CR3","unstructured":"Berstel, J.: Congruences plus que parfaites et langages alg\u00e9briques. Seminaire d'Informatique Th\u00e9orique, Institut de Programmation 1976?77, pp. 123?147"},{"key":"CR4","volume-title":"Theory of codes","author":"J. Berstel","year":"1985","unstructured":"Berstel, J., Perrin, D.: Theory of codes. New York: Academic Press 1985"},{"key":"CR5","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. J. Assoc. Comput. Mach.29 171?182 (1982)","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR6","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(82)90072-X","volume":"18","author":"R.V. Book","year":"1982","unstructured":"Book, R.V.: When is a monoid a group? The Church-Rosser case is tractable. Theor. Comput. Sci.18, 325?331 (1982)","journal-title":"Theor. Comput. Sci."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0304-3975(83)90005-1","volume":"23","author":"R.V. Book","year":"1983","unstructured":"Book, R.V.: Decidable sentences of Church-Rosser congruences. Theor. Comput. Sci.23, 301?312 (1983)","journal-title":"Theor. Comput. Sci."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/S0747-7171(87)80021-4","volume":"3","author":"R.V. Book","year":"1987","unstructured":"Book, R.V.: Thue systems as rewriting systems. J. Symbol. Computat.3, 39?68 (1987)","journal-title":"J. Symbol. Computat."},{"key":"CR9","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF02572815","volume":"22","author":"R.V. Book","year":"1981","unstructured":"Book, R.V., O'Dunlaing, C.: Thue congruences and the Church-Rosser property. Semigroup Forum22, 367?379 (1981)","journal-title":"Semigroup Forum"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1016\/0304-3975(81)90078-5","volume":"16","author":"R.V. Book","year":"1981","unstructured":"Book, R.V., O'Dunlaing, C.: Testing for the Church-Rosser property. Theor. Comput. Sci.16, 223?229 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"CR11","series-title":"Proc. 4th Workshop on Automated Deduction","first-page":"53","volume-title":"Reduction systems and small cancellation theory","author":"H. B\u00fccken","year":"1979","unstructured":"B\u00fccken, H.: Reduction systems and small cancellation theory. Proc. 4th Workshop on Automated Deduction, pp. 53?59. Austin: University of Texas 1979"},{"key":"CR12","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1016\/0021-8693(79)90238-2","volume":"57","author":"R.H. Gilman","year":"1979","unstructured":"Gilman, R.H.: Presentations of groups and monoids. J. Algebra57, 544?554 (1979)","journal-title":"J. Algebra"},{"key":"CR13","volume-title":"Introduction to automata theory, languages, and computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation. Reading: Addison-Wesley 1979"},{"key":"CR14","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1016\/B978-0-12-115350-2.50017-8","volume-title":"Formal language theory: perspectives and open problems","author":"G. Huet","year":"1980","unstructured":"Huet, G., Oppen, D.: Equations and rewrite rules. In: Book, R.V. (ed.) Formal language theory: perspectives and open problems, pp. 349?405. New York: Academic Press 1980"},{"key":"CR15","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H. Hunt","year":"1976","unstructured":"Hunt, H., Rosenkrantz, D., Szymanski, T.: On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. System Sci.12, 222?268 (1976)","journal-title":"J. Comput. System Sci."},{"key":"CR16","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0020-0190(85)90018-3","volume":"21","author":"M. Jantzen","year":"1985","unstructured":"Jantzen, M.: A note on a special one-rule semi-Thue system. Inform. Process. Lett.21, 135?140 (1985)","journal-title":"Inform. Process. Lett."},{"key":"CR17","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. Berlin Heidelberg New York: Springer 1988"},{"key":"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.: AnO(|T|3) algorithm for testing the Church-Rosser property of Thue systems. Theor. Comput. Sci.35, 109?114 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"CR19","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0304-3975(85)90023-4","volume":"35","author":"D. Kapur","year":"1985","unstructured":"Kapur, D., Narendran, P.: A finite Thue system with decidable word problem and without equivalent finite canonical system. Theor. Comput. Sci.35, 337?344 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"CR20","first-page":"263","volume-title":"Computational problems in abstract algebra","author":"D. Knuth","year":"1970","unstructured":"Knuth, D., Bendix, P.: Simple word problems in universal algebras. In: Leech, J. (ed.) Computational problems in abstract algebra, pp. 263?297. New York: Pergamon Press 1970"},{"key":"CR21","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D. Knuth","year":"1977","unstructured":"Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput.6, 323?350 (1977)","journal-title":"SIAM J. Comput."},{"key":"CR22","volume-title":"Semigroups and combinatorial applications","author":"G. Lallement","year":"1979","unstructured":"Lallement, G.: Semigroups and combinatorial applications. New York: John Wiley 1979"},{"key":"CR23","volume-title":"Canonical forms in finitely presented algebras","author":"P. LeChenadec","year":"1986","unstructured":"LeChenadec, P.: Canonical forms in finitely presented algebras. London New York: Pitman, John Wiley 1986"},{"key":"CR24","volume-title":"Combinatorial group theory","author":"R.C. Lyndon","year":"1977","unstructured":"Lyndon, R.C., Schupp, P.E.: Combinatorial group theory. Berlin Heidelberg New York: Springer 1977"},{"key":"CR25","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/0020-0190(87)90149-9","volume":"24","author":"K. Madlener","year":"1987","unstructured":"Madlener, K., Otto, F.: Using string-rewriting for solving the word problem for finitely presented groups. Inform. Process. Lett.24, 281?284 (1987)","journal-title":"Inform. Process. Lett."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0304-3975(89)90002-9","volume":"67","author":"K. Madlener","year":"1989","unstructured":"Madlener, K., Otto, F.: About the descriptive power of certain classes of finite stringrewriting systems. Theor. Comput. Sci.67, 143?172 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"CR27","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1016\/0021-8693(87)90136-0","volume":"108","author":"R. McNaughton","year":"1987","unstructured":"McNaughton, R., Narendran, P.: Special monoids and special Thue systems. J. Algebra108, 248?255 (1987)","journal-title":"J. Algebra"},{"key":"CR28","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1016\/S0747-7171(89)80028-8","volume":"7","author":"P. Narendran","year":"1989","unstructured":"Narendran, P., O'Dunlaing, C.: Cancellativity in finitely presented semigroups. J. Symbol. Comput.7, 457?472 (1989)","journal-title":"J. Symbol. Comput."},{"key":"CR29","doi-asserted-by":"crossref","unstructured":"Narendran, P., O'Dunlaing, C., Otto, F.: It is undecidable whether a finite special stringrewriting system presents a group. Discr. Math. (in press, 1990)","DOI":"10.1016\/0012-365X(91)90040-9"},{"key":"CR30","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0304-3975(85)90016-7","volume":"35","author":"P. Narendran","year":"1985","unstructured":"Narendran, P., Otto, F.: Complexity results on the conjugacy problem for monoids. Theor. Comput. Sci.35, 227?243 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"CR31","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0304-3975(86)90131-3","volume":"47","author":"P. Narendran","year":"1986","unstructured":"Narendran, P., Otto, F.: The problems of cyclic equality and conjugacy for finite complete rewriting systems. Theor. Comput. Sci.47, 27?38 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"CR32","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 weight-reducing and confluent Thue systems. Acta Inf.25, 573?591 (1988)","journal-title":"Acta Inf."},{"key":"CR33","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0304-3975(89)90167-9","volume":"68","author":"P. Narendran","year":"1989","unstructured":"Narendran, P., Otto, F.: Some polynomial-time algorithms for finite, monadic, Church-Rosser Thue systems. Theor. Comput. Sci.68, 319?332 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"CR34","doi-asserted-by":"crossref","first-page":"223","DOI":"10.2307\/1968867","volume":"43","author":"M. Newman","year":"1943","unstructured":"Newman, M.: On theories with a combinatorial definition of equivalence. Ann. Math.43, 223?243 (1943)","journal-title":"Ann. Math."},{"key":"CR35","unstructured":"Nivat, M., Benois, M.: Congruences parfaites et quasi-parfaites. Seminaire Dubreil, 25e Ann\u00e9e, 1971?72, 7-01-09"},{"key":"CR36","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/BF02573327","volume":"29","author":"F. Otto","year":"1984","unstructured":"Otto, F.: Conjugacy in monoids with a special Church-Rosser presentation is decidable. Semigroup Forum29, 223?240 (1984)","journal-title":"Semigroup Forum"},{"key":"CR37","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0304-3975(84)90090-2","volume":"33","author":"F. Otto","year":"1984","unstructured":"Otto, F.: Some undecidability results for non-monadic Church-Rosser Thue systems. Theor. Comput. Sci.33, 261?278 (1984)","journal-title":"Theor. Comput. Sci."},{"key":"CR38","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1090\/S0002-9947-1985-0800255-1","volume":"291","author":"F. Otto","year":"1985","unstructured":"Otto, F.: Elements of finite order for finite monadic Church-Rosser Thue systems. Transact. Am. Math. Soc.291, 629?637 (1985)","journal-title":"Transact. Am. Math. Soc."},{"key":"CR39","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF00268077","volume":"23","author":"F. Otto","year":"1986","unstructured":"Otto, F.: On deciding whether a monoid is a free monoid or is a group. Acta Inf.23, 99?110 (1986)","journal-title":"Acta Inf."},{"key":"CR40","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/BF02573208","volume":"33","author":"F. Otto","year":"1986","unstructured":"Otto, F.: On two problems related to cancellativity. Semigroup Forum33, 331?356 (1986)","journal-title":"Semigroup Forum"},{"key":"CR41","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1016\/0022-0000(87)90017-1","volume":"35","author":"F. Otto","year":"1987","unstructured":"Otto, F.: On deciding the confluence of a finite string-rewriting system on a given congruence class. J. Comput. System Sci.35, 285?310 (1987)","journal-title":"J. Comput. System Sci."},{"key":"CR42","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/0304-3975(89)90145-X","volume":"66","author":"L. Zhang","year":"1989","unstructured":"Zhang, L.: An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group. Theor. Comput. Sci.66, 55?64 (1989)","journal-title":"Theor. Comput. Sci."},{"key":"CR43","unstructured":"Zhang, L.: Conjugacy in special monoids. J. Algebra (in press, 1990)"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178585.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01178585\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01178585","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,23]],"date-time":"2024-01-23T15:51:40Z","timestamp":1706025100000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01178585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,5]]},"references-count":44,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1991,5]]}},"alternative-id":["BF01178585"],"URL":"https:\/\/doi.org\/10.1007\/bf01178585","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,5]]}}}