Các bài toán quyết định cho các hệ thống viết lại chuỗi đặc biệt hữu hạn có khả năng hội tụ trên một lớp đồng nhất nhất định

Adjan, S.: Defining relations and algorithmic problems for groups and semigroups. Proc. Steklov Inst. Math.85 (1966); English version: Am. Math. Soc. Transl.152 (1967) Benninghofen, B., Kemmerich, S., Richter, M.M.: Systems of reductions. (Lect. Notes Comput. Sci., vol. 277). Berlin Heidelberg New York: Springer 1987 Berstel, J.: Congruences plus que parfaites et langages algébriques. Seminaire d'Informatique Théorique, Institut de Programmation 1976–77, pp. 123–147 Berstel, J., Perrin, D.: Theory of codes. New York: Academic Press 1985 Book, R.V.: Confluent and other types of Thue systems. J. Assoc. Comput. Mach.29 171–182 (1982) Book, R.V.: When is a monoid a group? The Church-Rosser case is tractable. Theor. Comput. Sci.18, 325–331 (1982) Book, R.V.: Decidable sentences of Church-Rosser congruences. Theor. Comput. Sci.23, 301–312 (1983) Book, R.V.: Thue systems as rewriting systems. J. Symbol. Computat.3, 39–68 (1987) Book, R.V., O'Dunlaing, C.: Thue congruences and the Church-Rosser property. Semigroup Forum22, 367–379 (1981) Book, R.V., O'Dunlaing, C.: Testing for the Church-Rosser property. Theor. Comput. Sci.16, 223–229 (1981) Bücken, H.: Reduction systems and small cancellation theory. Proc. 4th Workshop on Automated Deduction, pp. 53–59. Austin: University of Texas 1979 Gilman, R.H.: Presentations of groups and monoids. J. Algebra57, 544–554 (1979) Hopcroft, J., Ullman, J.: Introduction to automata theory, languages, and computation. Reading: Addison-Wesley 1979 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 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) Jantzen, M.: A note on a special one-rule semi-Thue system. Inform. Process. Lett.21, 135–140 (1985) Jantzen, M.: Confluent string rewriting. Berlin Heidelberg New York: Springer 1988 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) 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) 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 Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in strings. SIAM J. Comput.6, 323–350 (1977) Lallement, G.: Semigroups and combinatorial applications. New York: John Wiley 1979 LeChenadec, P.: Canonical forms in finitely presented algebras. London New York: Pitman, John Wiley 1986 Lyndon, R.C., Schupp, P.E.: Combinatorial group theory. Berlin Heidelberg New York: Springer 1977 Madlener, K., Otto, F.: Using string-rewriting for solving the word problem for finitely presented groups. Inform. Process. Lett.24, 281–284 (1987) Madlener, K., Otto, F.: About the descriptive power of certain classes of finite stringrewriting systems. Theor. Comput. Sci.67, 143–172 (1989) McNaughton, R., Narendran, P.: Special monoids and special Thue systems. J. Algebra108, 248–255 (1987) Narendran, P., O'Dunlaing, C.: Cancellativity in finitely presented semigroups. J. Symbol. Comput.7, 457–472 (1989) Narendran, P., O'Dunlaing, C., Otto, F.: It is undecidable whether a finite special stringrewriting system presents a group. Discr. Math. (in press, 1990) Narendran, P., Otto, F.: Complexity results on the conjugacy problem for monoids. Theor. Comput. Sci.35, 227–243 (1985) Narendran, P., Otto, F.: The problems of cyclic equality and conjugacy for finite complete rewriting systems. Theor. Comput. Sci.47, 27–38 (1986) Narendran, P., Otto, F.: Elements of finite order for finite weight-reducing and confluent Thue systems. Acta Inf.25, 573–591 (1988) Narendran, P., Otto, F.: Some polynomial-time algorithms for finite, monadic, Church-Rosser Thue systems. Theor. Comput. Sci.68, 319–332 (1989) Newman, M.: On theories with a combinatorial definition of equivalence. Ann. Math.43, 223–243 (1943) Nivat, M., Benois, M.: Congruences parfaites et quasi-parfaites. Seminaire Dubreil, 25e Année, 1971–72, 7-01-09 Otto, F.: Conjugacy in monoids with a special Church-Rosser presentation is decidable. Semigroup Forum29, 223–240 (1984) Otto, F.: Some undecidability results for non-monadic Church-Rosser Thue systems. Theor. Comput. Sci.33, 261–278 (1984) Otto, F.: Elements of finite order for finite monadic Church-Rosser Thue systems. Transact. Am. Math. Soc.291, 629–637 (1985) Otto, F.: On deciding whether a monoid is a free monoid or is a group. Acta Inf.23, 99–110 (1986) Otto, F.: On two problems related to cancellativity. Semigroup Forum33, 331–356 (1986) 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) 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) Zhang, L.: Conjugacy in special monoids. J. Algebra (in press, 1990)