×

About the descriptive power of certain classes of finite string-rewriting systems. (English) Zbl 0697.20017

This paper is a survey of results concerning classification of monoids and groups presented by certain types of rewriting systems. It contains a large sampling of results, including proofs for some of the simpler ones, and contains an extensive bibliography of 61 entries. It also contains a number of examples which illuminate the results, or in some cases, the limitations of the results.
A finite set \(\Sigma\), the alphabet, and a finite set \(R\subset \Sigma^*\times \Sigma^*\), the rewriting rules, form a presentation for a monoid \(M_ R\), often called the syntactic monoid, namely, the quotient of the free monoid \(\Sigma^*\) by the congruence generated by R. Group presentations by rewriting systems are defined analogously, but with the usual convention of providing a second copy of \(\Sigma\) to denote the inverses of the elements of \(\Sigma\) and by providing outside of the set R the relations making corresponding elements in the two copies of \(\Sigma\) inverses of each other. The difference between a presentation by a rewriting system and a presentation in the usual sense is that reductions using the rewriting system can be considered to have a sense of direction - derivations in the sense of formal language theory.
Topics considered in the paper range from questions of decidability to classifications of monoid- or group-theoretic properties in terms of language-theoretic properties to questions of computational complexity. Numerous technical, but reasonable, conditions are attached to the rewriting systems, but these cannot be reproduced in the space of this review. A sampling of results may give a flavor of the paper.
If a monoid \(M_ R\) has a presentation such that the class of 1 is a regular, or context-free language, then every presentation has this property. Hence, the monoid can be called regular or context-free.
A group is regular if and only if it is finite.
A finitely generated group is context-free if and only if it contains a subgroup of finite index which is a free group, i.e., is virtually free.
Let R be a free, weight-reducing, and confluent string-rewriting system on \(\Sigma\), and let L be a regular set of irreducible words. If the monoid \(M_ R\) is a group, then \([L]_ R\), the set of words in \(\Sigma^*\) equivalent to some word in L, is a deterministic context- free language.
If \(E_ n\) (n\(\geq 0)\) denote the complexity classes of the Gregorczyk hierarchy, then for all integers m, n with \(3\leq n<m\) there is a finite canonical string-rewriting system R on an alphabet \(\Sigma\) such that
(a) the word problem of \(M_ R\) is of intrinsic complexity \(E_ n- E_{n-1}\), and
(b) the derivational complexity \(f_ R\) of R belongs to \(E_ m-E_{m- 1}.\)
There exist finitely presented monoids and groups having a decidable word problem but which do not admit any presentation by a finite canonical string-rewriting system. However, for every finitely presented monoid with a decidable word problem there exists a presentation by a canonical two-level rewriting system. (Here canonical means that every word reduces to a unique normal form. A two-level rewriting system consists of a pair of sets of rewriting rules such that one set is applied after the other.)
Reviewer: W.R.Nico

MSC:

20F05 Generators, relations, and presentations of groups
68Q45 Formal languages and automata
68Q65 Abstract data types; algebraic specification
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
20M05 Free semigroups, generators and relations, word problems
20M35 Semigroups in automata theory, linguistics, etc.
03D05 Automata and formal grammars in connection with logical questions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anissimov, A. V., Group languages, Cybernetics, 7, 594-601 (1971)
[2] Anissimov, A. V.; Seifert, F. D., Zur algebraischen Charakteristik der durch kontext-freie Sprachen definierten Gruppen, Elektron. Informationsverarb. Kybernetic, 11, 695-702 (1975) · Zbl 0322.68047
[3] Autebert, J. M.; Boasson, L.; Senizergues, G., Langages de parentheses, langages NTS et morphismes inverses, RAIRO Inform. Théor., 18, 327-344 (1984) · Zbl 0547.68075
[4] Autebert, J. M.; Boasson, L.; Senizergues, G., Groups and NTS languages, J. Comput. System Sci., 35, 243-267 (1987) · Zbl 0626.68056
[5] Avenhaus, J.; Book, R. V.; Squier, C., On expressing commutativity by finite Church-Rosser presentations: a note on commutative monoids, RAIRO Inform. Théor., 18, 47-52 (1984) · Zbl 0542.20038
[6] Avenhaus, J.; Madlener, K., On groups defined by monadic Thue systems, (Algebra, Combinatorics and Logic in Computer Science. Algebra, Combinatorics and Logic in Computer Science, Colloquia Mathematica Societatis Janos Bolyai, 42 (1983), Gyor: Gyor Hungary), 63-71 · Zbl 0608.20045
[7] Avenhaus, J.; Madlener, K.; Otto, F., Groups presented by finite two-monadic Church-Rosser Thue systems, Trans. Amer. Math. Soc., 297, 427-443 (1986) · Zbl 0604.20034
[8] Bauer, G., Zur Darstellung von Monoiden durch konfluente Regelsysteme, (Doctoral Dissertation (1981), Fachbereich Informatik, Universität Kaiserslautern)
[9] Bauer, G., \(n\)-Level rewriting systems, Theoret. Comput. Sci., 40, 85-99 (1985) · Zbl 0606.68025
[10] Bauer, G.; Otto, F., Finite complete rewriting systems and the complexity of the word problem, Acta Inform., 21, 521-540 (1984) · Zbl 0535.68019
[11] Beeri, C., An improvement on Valiant’s decision procedure for equivalence of deterministic finite turn pushdown machines, Theoret. Comput. Sci., 3, 305-320 (1976) · Zbl 0361.68082
[12] Benninghofen, B.; Kemmerich, S.; Richter, M. M., Systems of Reductions, (Lecture Notes in Computer Science, 227 (1987), Springer: Springer Berlin) · Zbl 0636.68027
[13] Bieri, R., Homological Dimension of Discrete Groups, (Queen Mary College Mathematics Notes (1976), Queen Mary College, Univ. of London) · Zbl 0357.20027
[14] Bieri, R., A connection between the integral homology and the centre of a rational linear group, Math. Z., 170, 263-266 (1980) · Zbl 0427.20042
[15] Boasson, L.; Senizergues, G., NTS languages are congruential and deterministic, J. Comput. System Sci., 31, 332-342 (1985) · Zbl 0604.68087
[16] Book, R. V., Confluent and other types of Thue systems, J. Assoc. Comput. Mach., 29, 171-182 (1982) · Zbl 0478.68032
[17] Book, R. V., Decidable sentences of Church-Rosser congruences, Theoret. Comput. Sci., 24, 301-312 (1983) · Zbl 0525.68015
[18] Book, R. V., Thue systems as rewriting systems, J. Symbolic Comput., 3, 39-68 (1987) · Zbl 0638.68091
[19] Book, R. V.; Jantzen, M.; Wrathall, C., Monadic Thue systems, Theoret. Comput. Sci., 19, 231-251 (1982) · Zbl 0488.03020
[20] K.S. Brown, Finiteness properties of groups, Preprint.; K.S. Brown, Finiteness properties of groups, Preprint. · Zbl 0613.20033
[21] Buecken, H., Reduction systems and small cancellation theory, Proc. 4th Workshop on Automated Deduction, 53-59 (1979)
[22] Cochet, Y., Church-Rosser congruences on free semigroups, (Algebraic theory of Semigroups. Algebraic theory of Semigroups, Colloquia Mathematica Societatis Janos Bolyai, 20 (1976), North-Holland: North-Holland Amsterdam), 51-60 · Zbl 0408.20054
[23] Diekert, V., Complete semi-Thue systems for abelian groups, Theoret. Comput. Sci., 44, 199-208 (1986) · Zbl 0609.68028
[24] Diekert, V., Some remarks on Church-Rosser Thue presentations, (Proc. STACS 87. Proc. STACS 87, Lecture Notes in Computer Science, 247 (1987), Springer: Springer Berlin), 272-285 · Zbl 0636.20023
[25] Diekert, V., Some properties of weight-reducing presentations, (Tech. Report TUM-18710 (1987), Institut für Informatik, Technische Universität München)
[26] Dunwoody, M. J., The accessibility of finitely presented groups, Invent. Math., 81, 449-457 (1985) · Zbl 0572.20025
[27] Gilman, R., Presentations of groups and monoids, J. Algebra, 57, 544-554 (1971) · Zbl 0403.20022
[28] Gilman, R., Computations with rational subsets of confluent groups, (Proc. EUROSAM 84. Proc. EUROSAM 84, Lecture Notes in Computer Science, 174 (1984), Springer: Springer Berlin), 207-212
[29] Grzegorczyk, A., Some classes of recursive functions, Rozprawy Math., 4, 1-45 (1953)
[30] Haring-Smith, R. H., Groups and simple languages, Trans. Amer. Math. Soc., 279, 337-356 (1983) · Zbl 0518.20030
[31] Jantzen, M., On a special monoid with a single defining relation, Theoret. Comput. Sci., 16, 61-73 (1981) · Zbl 0482.20043
[32] Jantzen, M., A note on a special one-rule semi-Thue system, Inform. Process. Lett., 21, 135-140 (1985) · Zbl 0581.68030
[33] Jantzen, M., Confluent String Rewriting (1988), Springer: Springer Berlin · Zbl 1097.68572
[34] Kapur, D.; Narendran, P., A finite Thue system with decidable word problem and without equivalent finite canonical system, Theoret. Comput. Sci., 35, 337-344 (1985) · Zbl 0588.03023
[35] Kapur, D.; Narendran, P., The Knuth-Bendix completion procedure and Thue systems, SIAM J. Comput., 14, 1052-1072 (1985) · Zbl 0576.68010
[36] Kemmerich, S., Unendliche Reduktionssysteme, (Doctoral Dissertation (1983), Fachbereich Mathematik: Fachbereich Mathematik TH Aachen) · Zbl 0619.68034
[37] Knuth, D.; Bendix, P., Simple word problems in universal algebra, (Leech, J., Computational Problems in Abstract Algebra (1970), Pergamon: Pergamon Oxford), 263-297 · Zbl 0188.04902
[38] LeChenadec, Ph., Canonical Forms in Finitely Presented Algebras (1986), Pitman: Pitman London, Wiley, New York
[39] Lyndon, R. C.; Schupp, P. E., Combinatorial Group Theory (1977), Springer: Springer Berlin · Zbl 0368.20023
[40] Madlener, K.; Otto, F., Pseudo-natural algorithms for the word problem for finitely presented monoids and groups, J. Symbolic Comput., 1, 383-418 (1985) · Zbl 0591.20038
[41] Madlener, K.; Otto, F., Groups presented by finite length-reducing string-rewriting systems, (Tech. Report 86-28 (1986), Department of Computer Science: Department of Computer Science SUNY Albany). (Lescanne, P., Rewriting Techniques and Applications. Rewriting Techniques and Applications, Lecture Notes Computer Science, 256 (1987), Springer: Springer Berlin), 133-144
[42] Madlener, K.; Otto, F., Pseudo-natural algorithms for finitely generated presentations of monoids and groups, J. Symbolic Comput., 5, 339-358 (1988) · Zbl 0665.20019
[43] Madlener, K.; Otto, F., Commutativity in groups presented by finite Church-Rosser Thue systems, RAIRO Inform. Théor., 22, 93-111 (1988) · Zbl 0649.20030
[44] Madlener, K.; Otto, F., On groups having finite monadic Church-Rosser presentations, (Jürgensen, H.; Lallement, G.; Weinert, H. J., Semigroups, Theory and Applications. Semigroups, Theory and Applications, Lecture Notes in Mathematics, 1320 (1988), Springer: Springer Berlin), 218-234 · Zbl 0672.20015
[45] Magnus, W.; Karrass, A.; Solitar, D., Combinatorial Group Theory (1976), Dover: Dover New York
[46] Martin, U., How to choose the weights in the Knuth-Bendix ordering, (Lescanne, P., Rewriting Techniques and Applications. Rewriting Techniques and Applications, Lecture Notes Computer Science, 256 (1987), Springer: Springer Berlin), 42-53 · Zbl 0638.68108
[47] Muller, D. E.; Schupp, P. E., Groups, the theory of ends, and context-free languages, J. Comput. System Sci., 26, 295-310 (1983) · Zbl 0537.20011
[48] Narendran, P.; Otto, F., Complexity results on the conjugacy problem for monoids, Theoret. Comput. Sci., 35, 227-243 (1985) · Zbl 0588.03022
[49] 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
[50] 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
[51] Nivat, M., On some families of languages related to the Dyck languages, Proc. 2nd. ACM Symp. on Theory of Comput., 221-225 (1970)
[52] O’Dunlaing, C., Infinite regular Thue systems, Theoret. Comput. Sci., 25, 171-192 (1983) · Zbl 0512.03018
[53] Otto, F., Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group, Theoret. Comput. Sci., 32, 249-260 (1984) · Zbl 0555.20036
[54] Otto, F., On deciding whether a monoid is a free monoid or is a group, Acta Inform., 23, 99-110 (1986) · Zbl 0592.20059
[55] 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) · Zbl 0645.03033
[56] G. Senizergues, About the description of deterministic context-free languages by confluent rewriting systems, in:Proc. Coll. on Resolution of Equations in Algebraic Structures; G. Senizergues, About the description of deterministic context-free languages by confluent rewriting systems, in:Proc. Coll. on Resolution of Equations in Algebraic Structures · Zbl 0672.68040
[57] Squier, C. C., Word problems and a homological finiteness condition for monoids, J. Pure Appl. Algebra, 49, 201-217 (1987) · Zbl 0648.20045
[58] C.C. Squier, A finiteness condition for rewriting systems, submitted for publication.; C.C. Squier, A finiteness condition for rewriting systems, submitted for publication.
[59] Stallings, J. R., A finitely presented group whose 3-dimensional integral homology is not finitely generated, Amer. J. Math., 85, 541-543 (1963) · Zbl 0122.27301
[60] Valiant, L. G., The equivalence problem for deterministic finite-turn pushdown automata, Inform. and Control, 25, 123-133 (1974) · Zbl 0285.68025
[61] Weihrauch, K., Teilklassen primitiv-rekursiver Wortfunktionen, Report No. 91 (1974), GMD Bonn · Zbl 0293.02026
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.