Narendran, Paliath; Otto, Friedrich Some polynomial-time algorithms for finite monadic Church-Rosser Thue systems. (English) Zbl 0677.68050 Theor. Comput. Sci. 68, No. 3, 319-332 (1989). Summary: Based on a careful analysis of reduction sequences in monadic Thue systems we show that some uniform decision problems, among them the uniform conjugacy problem, are decidable in polynomial time for finite monadic Church-Rosser Thue systems. On the other hand, an example of a decision problem is exhibited that is undecidable even for this class of Thue systems. Cited in 2 Documents MSC: 68Q25 Analysis of algorithms and problem complexity 68Q65 Abstract data types; algebraic specification 03D03 Thue and Post systems, etc. 03B25 Decidability of theories and sets of sentences 68T15 Theorem proving (deduction, resolution, etc.) (MSC2010) 68T99 Artificial intelligence Keywords:finite monadic Church-Rosser Thue systems; rewriting systems; uniform decision problems; uniform conjugacy problem PDFBibTeX XMLCite \textit{P. Narendran} and \textit{F. Otto}, Theor. Comput. Sci. 68, No. 3, 319--332 (1989; Zbl 0677.68050) Full Text: DOI References: [1] Book, R. V., Confluent and other types of Thue systems, J. Assoc. Comput. Mach., 29, 171-182 (1982) · Zbl 0478.68032 [2] Book, R. V., Decidable sentences of Church-Rosser congruences, Theoret. Comput. Sci., 24, 301-312 (1983) · Zbl 0525.68015 [3] Book, R. V., Thue systems and the Church-Rosser property; replacement systems, specification of formal languages, and presentations of monoids, (Cummings, L., Combinatorics on Words: Progress and Perspectives (1983), Academic Press: Academic Press Canada), 1-38 · Zbl 0563.68062 [4] Book, R. V., Thue systems as rewriting systems, J. Symbolic Comput., 3, 39-68 (1987) · Zbl 0638.68091 [5] Gilman, R., Presentations of groups and monoids, J. Algebra, 57, 544-554 (1979) · Zbl 0403.20022 [6] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701 [7] Kapur, D.; Narendran, P., The Knuth-Bendix completion procedure and Thue systems, SIAM J. Comput., 14, 1052-1072 (1985) · Zbl 0576.68010 [8] Lyndon, R.; Schutzenberger, M., The equation \(a^M=b^{N\) · Zbl 0106.02204 [9] Narendran, P.; O’Dunlaing, C., Cancellativity in finitely presented semigroups, J. Symbolic Comput., 7, 457-472 (1989) · Zbl 0682.20046 [10] Narendran, P.; Otto, F., Complexity results on the conjugacy problem for monoids, Theoret. Comput. Sci., 35, 227-243 (1985) · Zbl 0588.03022 [11] Narendran, P.; Otto, F., The problems of cyclic equality and conjugacy for finite complete rewriting systems, Theoret. Comput. Sci., 47, 27-38 (1986) · Zbl 0619.68033 [12] Narendran, P.; Otto, F., Elements of finite order for finite weight-reducing and confluent Thue systems, Acta Inform., 25, 573-591 (1988) · Zbl 0673.68025 [13] Narendran, P.; Otto, F.; Winklmann, K., The uniform conjugacy problem for finite Church-Rosser Thue systems is NP-complete, Inf. Control, 63, 58-66 (1984) · Zbl 0592.03025 [14] Otto, F., Conjugacy in monoids with a special Church-Rosser presentation is decidable, Semigroup Forum, 29, 223-240 (1984) · Zbl 0551.20044 [15] Otto, F., Elements of finite order for finite monadic Church-Rosser Thue systems, Trans. Amer. Math. Soc., 291, 629-637 (1985) · Zbl 0583.20054 [16] Otto, F., On two problems related to cancellativity, Semigroup Forum, 33, 331-356 (1986) · Zbl 0584.20046 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.