×

zbMATH — the first resource for mathematics

The conjugacy problem in subgroups of right-angled Artin groups. (English) Zbl 1181.20030
The authors re-prove first that the word problem in graph groups, [see H. Servatius, J. Algebra 126, No. 1, 34-60 (1989; Zbl 0682.20022)], or right-angled Artin groups, admits a linear time solution by introducing the notion of ‘piling’ as a tool. Then they provide a new proof to the conjugacy problem, which in turn yields a linear time algorithm for solving the conjugacy problem in a class of subgroups of graph groups. This class contains all braid groups and state complex groups and has been previously studied by J. Crisp and B. Wiest [in Trans. Am. Math. Soc. 359, No. 11, 5485-5503 (2007; Zbl 1186.20027) and Algebr. Geom. Topol. 4, 439-472 (2004; Zbl 1057.20028)] and independently by F. Haglund and D. T. Wiese [in Geom. Funct. Anal. 17, No. 5, 1551-1620 (2007; Zbl 1155.53025)]. The special properties required for the algorithm to work are expressed geometrically and termed ‘the convexity property’ and ‘the injectivity property’.

MSC:
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F36 Braid groups; Artin groups
20F65 Geometric group theory
20E06 Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrams, Configuration spaces of colored graphs, Geom. Dedicata 92 pp 185– (2002) · Zbl 1049.20023 · doi:10.1023/A:1019662529807
[2] Abrams, Finding topology in a factory: configuration spaces, Amer. Math. Monthly 109 ((2)) pp 140– (2002) · Zbl 1051.68127 · doi:10.2307/2695326
[3] Abrams, State complexes for metamorphic robots, Internat. J. Robot. Res. 23 ((7-8)) pp 809– (2004)
[4] A. V. Aho J. E. Hopcroft J. D. Ullman The design and analysis of computer algorithms 1974 London Addison-Wesley · Zbl 0326.68005
[5] Baudisch, Subgroups of semifree groups, Acta Math. Acad. Sci. Hungar 38 pp 19– (1981) · Zbl 0417.20033 · doi:10.1007/BF01917515
[6] Boyer, A fast string searching algorithm, Commun. ACM 20 ((10)) pp 762– (1977) · Zbl 1219.68165 · doi:10.1145/359842.359859
[7] M. R. Bridson A. Haefliger Metric spaces of non-positive curvature 1999 319 Berlin Springer Springer Grundlehren Series
[8] P. Cartier D. Foata Problèmes combinatoires de commutation et réarrangements 1969 85 Berlin-New York Springer Lecture Notes in Mathematics
[9] Charney, An introduction to right-angled Artin groups, Geom. Dedicata 125 pp 141– (2007) · Zbl 1152.20031 · doi:10.1007/s10711-007-9148-6
[10] Crisp, Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups, Algebr. Geom. Topol. 4 pp 439– (2004) · Zbl 1057.20028 · doi:10.2140/agt.2004.4.439
[11] Crisp, Quasi-isometrically embedded subgroups of braid and diffeomorphism groups, Trans. Amer. Math. Soc. 359 pp 5485– (2007) · Zbl 1186.20027 · doi:10.1090/S0002-9947-07-04332-2
[12] Duboc, Commutation dans les monoïdes libres, un cadre théorique pour l’étude du parallélisme, in: Doctoral thesis, University of Rouen, Rouen (1986)
[13] Epstein, The linearity of the conjugacy problem in word-hyperbolic groups, Internat. J. Algebra Comput. 16 ((2)) pp 287– (2006) · Zbl 1141.20028 · doi:10.1142/S0218196706002986
[14] Farley, Discrete Morse theory and graph braid groups, Algebr. Geom. Topol. 5 pp 1075– (2005) · Zbl 1134.20050 · doi:10.2140/agt.2005.5.1075
[15] Farley, On the cohomology rings of tree braid groups, J. Pure Appl. Algebra 212 pp 53– (2008) · Zbl 1137.20027 · doi:10.1016/j.jpaa.2007.04.011
[16] Ghrist, The geometry and topology of reconfiguration, Adv. Appl. Math. 38 pp 302– (2007) · Zbl 1124.68109 · doi:10.1016/j.aam.2005.08.009
[17] D. Gusfield Algorithms on strings, trees, and sequences: computer science and computational biology 1997 Cambridge Cambridge University Press · Zbl 0934.68103 · doi:10.1017/CBO9780511574931
[18] Haglund, Special cube complexes, Geom. Funct. Anal. 17 ((5)) pp 1551– (2008) · Zbl 1155.53025 · doi:10.1007/s00039-007-0629-4
[19] Haglund, Coxeter groups are special, in: Preprint (2008)
[20] Knuth, Fast pattern-matching algorithms, SIAM J. Comput. 6 ((2)) pp 323– (1977) · Zbl 0372.68005 · doi:10.1137/0206024
[21] Krob, Computing the average parallelism in trace monoids, Discrete Math. 273 pp 131– (2003) · Zbl 1076.68041 · doi:10.1016/S0012-365X(03)00233-4
[22] Lalonde, Contribution à l’étude des empilements, in: Doctoral thesis, University of Quebec and Montreal, Montreal (1990)
[23] Liu, Efficient solution of some problems in free partially commutative monoids, Inform. and Comput. 89 pp 180– (1990) · Zbl 0719.68036 · doi:10.1016/0890-5401(90)90010-F
[24] Niblo, The geometry of cube complexes and the complexity of their fundamental groups, Topology 37 pp 621– (1998) · Zbl 0911.57002 · doi:10.1016/S0040-9383(97)00018-9
[25] Sabalka, Embedding right-angled Artin groups into graph braid groups, Geom. Dedicata 124 pp 191– (2007) · Zbl 1130.20036 · doi:10.1007/s10711-006-9101-0
[26] Servatius, Automorphisms of graph groups, J. Algebra 126 pp 34– (1987) · Zbl 0682.20022 · doi:10.1016/0021-8693(89)90319-0
[27] G. Stephen String searching algorithms 1994 River Edge World Scientific
[28] Van Wyk, Graph groups are biautomatic, J. Pure Appl. Algebra 94 pp 341– (1994) · Zbl 0812.20018 · doi:10.1016/0022-4049(94)90015-9
[29] X. Viennot Algèbres de Lie libre et monoïdes libres 1978 691 Berlin Springer Lecture Notes in Mathematics
[30] C. Wrathall D.Z. Du G. Hu Free partially commutative groups Combinatorics, computing and complexity Norwell, MA, 1989 Kluwer Academic/Science Press
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.