×

Gilman’s conjecture. (English) Zbl 1418.20009

R. Gilman [Lect. Notes Comput. Sci. 174, 207–212 (1984; Zbl 0549.68025)] conjectured that a group \(G\) is presented by a finite, monadic, confluent rewriting system if and only if \(G\) is the free product of a finitely generated free group with finitely many finite groups. In some special cases, Gilman’s conjecture was proved by J. Avenhaus et al., [Trans. Am. Math. Soc. 297, 427–443 (1986; Zbl 0604.20034)] and the second author [Bull. Aust. Math. Soc. 91, No. 3, 426–434 (2015); Zbl 1335.20037]. Here, the authors prove the conjecture in its full generality (Theorem 5.3). They also give a new proof of Y. Cochet’s result [In: Algebraic theory of semigroups. Amsterdam, Oxford, New York: North-Holland Publishing Company. 51–60 (1979; Zbl 0408.20054)] that a group \(G\) is presented by a finite, special, confluent rewriting system if and only if \(G\) is the free product finitely many cyclic groups (Theorem 4.8).

MSC:

20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F05 Generators, relations, and presentations of groups
68Q42 Grammars and rewriting systems
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Autebert, Jean-Michel; Boasson, Luc; Sénizergues, Géraud, Groups and NTS languages, J. Comput. System Sci., 35, 2, 243-267, (1987) · Zbl 0626.68056
[2] Avenhaus, J.; Madlener, K., On groups defined by monadic thue systems, (Algebra, Combinatorics and Logic in Computer Science, Vol. I, II, Győr, 1983, Colloq. Math. Soc. János Bolyai, vol. 42, (1986), North-Holland Amsterdam), 63-71 · Zbl 0608.20045
[3] Avenhaus, J.; Madlener, K.; Otto, F., Groups presented by finite two-monadic church-rosser thue systems, Trans. Amer. Math. Soc., 297, 2, 427-443, (1986) · Zbl 0604.20034
[4] Book, Ronald V., Confluent and other types of thue systems, J. ACM, 29, 1, 171-182, (January 1982)
[5] Cochet, Y., Church-rosser congruences on free semigroups, (Algebraic Theory of Semigroups, Proc. Sixth Algebraic Conf., Szeged, 1976, Colloq. Math. Soc. János Bolyai, vol. 20, (1979), North-Holland Amsterdam, New York), 51-60 · Zbl 0408.20054
[6] Volker, Diekert, Some remarks on presentations by finite church-rosser thue systems, (STACS 87, Passau, 1987, Lecture Notes in Comput. Sci., vol. 247, (1987), Springer Berlin), 272-285 · Zbl 0636.20023
[7] Dunwoody, M. J., The accessibility of finitely presented groups, Invent. Math., 81, 3, 449-457, (1985) · Zbl 0572.20025
[8] Gilman, Robert H.; Hermiller, Susan; Holt, Derek F.; Rees, Sarah, A characterisation of virtually free groups, Arch. Math. (Basel), 89, 4, 289-295, (2007) · Zbl 1139.20029
[9] Gilman, Robert H., Computations with rational subsets of confluent groups, (EUROSAM 84, Cambridge, 1984, Lecture Notes in Comput. Sci., vol. 174, (1984), Springer Berlin), 207-212 · Zbl 0549.68025
[10] Karrass, A.; Pietrowski, A.; Solitar, D., Finite and infinite cyclic extensions of free groups, Collection of Articles Dedicated to the Memory of Hanna Neumann, IV, J. Aust. Math. Soc., 16, 458-466, (1973) · Zbl 0299.20024
[11] Madlener, Klaus; Otto, Friedrich, Groups presented by certain classes of finite length-reducing string-rewriting systems, (Rewriting Techniques and Applications, Bordeaux, 1987, Lecture Notes in Comput. Sci., vol. 256, (1987), Springer Berlin), 133-144 · Zbl 0636.20022
[12] Madlener, Klaus; Otto, Friedrich, On groups having finite monadic church-rosser presentations, (Semigroups, Theory and Applications, Oberwolfach, 1986, Lecture Notes in Math., vol. 1320, (1988), Springer Berlin), 218-234 · Zbl 0672.20015
[13] Muller, David E.; Schupp, Paul E., Groups, the theory of ends, and context-free languages, J. Comput. System Sci., 26, 3, 295-310, (1983) · Zbl 0537.20011
[14] Piggott, Adam, On groups presented by monadic rewriting systems with generators of finite order, Bull. Aust. Math. Soc., 91, 3, 426-434, (2015) · Zbl 1335.20037
[15] Parkes, Duncan W.; Shavrukov, V. Yu.; Thomas, Richard M., Monoid presentations of groups by finite special string-rewriting systems, RAIRO Theor. Inform. Appl., 38, 3, 245-256, (2004) · Zbl 1071.20037
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.