×

Logspace computations in graph products. (English) Zbl 1335.68103

Summary: We consider three important and well-studied algorithmic problems in group theory: the word, geodesic, and conjugacy problem. We show transfer results from individual groups to graph products. We concentrate on logspace complexity because the challenge is actually in small complexity classes, only. The most difficult transfer result is for the conjugacy problem. We have a general result for graph products, but even in the special case of a graph group the result is new. Graph groups are closely linked to the theory of Mazurkiewicz traces which form an algebraic model for concurrent processes. Our proofs are combinatorial and based on well-known concepts in trace theory. We also use rewriting techniques over traces. For the group-theoretical part we apply Bass-Serre theory. But as we need explicit formulae and as we design concrete algorithms all our group-theoretical calculations are completely explicit and accessible to non-specialists.

MSC:

68Q25 Analysis of algorithms and problem complexity
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C76 Graph operations (line graphs, products, etc.)
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bestvina, M.; Brady, N., Morse theory and finiteness properties of groups, Invent. Math., 129, 3, 445-470 (1997) · Zbl 0888.20021
[2] Cai, J.-Y., Parallel computation over hyperbolic groups, (Proc. 24th ACM Symp. on Theory of Computing. Proc. 24th ACM Symp. on Theory of Computing, STOC 92 (1992), ACM-press), 106-115
[3] Crisp, J.; Godelle, E.; Wiest, B., The conjugacy problem in right-angled Artin groups and their subgroups, J. Topol., 2, 3, 442-460 (2009) · Zbl 1181.20030
[4] Crisp, J.; Wiest, B., Embeddings of graph braid and surface groups in right-angled Artin groups and braid groups, Algebr. Geom. Topol., 4, 439-472 (2004) · Zbl 1057.20028
[5] Diekert, V.; Kausch, J., Logspace computations in graph products, (Nabeshima, K.; Nagasaka, K.; Winkler, F.; Szántó, Á., ISSAC (2014), ACM), 138-145 · Zbl 1325.68106
[6] Diekert, V.; Kausch, J.; Lohrey, M., Logspace computations in Coxeter groups and graph groups, (Computational and Combinatorial Group Theory and Cryptography. Computational and Combinatorial Group Theory and Cryptography, Contemporary Mathematics, vol. 582 (2012), Amer. Math. Soc.), 77-94, Journal version of LATIN 2012, Lect. Notes Comput. Sci. 7256 (2012) 243-254 · Zbl 1283.20044
[7] Diekert, V.; Lohrey, M., Word equations over graph products, Int. J. Algebra Comput., 18, 493-533 (2008), Conference version in FSTTCS 2003 · Zbl 1186.20041
[8] Diekert, V.; Muscholl, A., Solvability of equations in free partially commutative groups is decidable, Int. J. Algebra Comput., 16, 1047-1070 (2006), Journal version of ICALP 2001, Lect. Notes Comput. Sci. 2076, 543-554 · Zbl 1112.03009
[9] (Diekert, V.; Rozenberg, G., The Book of Traces (1995), World Scientific: World Scientific Singapore)
[10] Droms, C., Graph groups, coherence and three-manifolds, J. Algebra, 106, 2, 484-489 (1985) · Zbl 0692.05035
[11] Droms, C.; Lewin, J.; Servatius, H., The length of elements in free solvable groups, Proc. Am. Math. Soc., 119, 27-33 (1993) · Zbl 0798.20026
[12] Duboc, Ch., On some equations in free partially commutative monoids, Theor. Comput. Sci., 46, 159-174 (1986) · Zbl 0605.20062
[13] Elder, M., A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups, Ill. J. Math., 54, 1, 109-128 (2010) · Zbl 1234.20048
[14] Elder, M.; Elston, G.; Ostheimer, G., On groups that have normal forms computable in logspace, J. Algebra, 381, 260-281 (2013) · Zbl 1279.20042
[15] Elder, M.; Rechnitzer, A., Some geodesic problems in groups, Groups Complex. Cryptol., 2, 2, 223-229 (2010) · Zbl 1222.20023
[16] Haubold, N.; Lohrey, M.; Mathissen, C., Compressed decision problems for graph products and applications to (outer) automorphism groups, Int. J. Appl. Cryptogr., 22 (2012) · Zbl 1267.20050
[17] Hsu, T.; Wise, D. T., On linear and residual properties of graph products, Mich. Math. J., 46, 2, 251-259 (1999) · Zbl 0962.20016
[18] Jung, H., Depth efficient transformations of arithmetic into boolean circuits, (Budach, L., Fundamentals of Computation Theory. Fundamentals of Computation Theory, Lecture Notes in Computer Science., vol. 199 (1985), Springer: Springer Berlin Heidelberg), 167-174
[19] Keller, R. M., Parallel program schemata and maximal parallelism I. Fundamental results, J. ACM, 20, 3, 514-537 (1973) · Zbl 0273.68011
[20] Lipton, R. J.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 522-526 (1977) · Zbl 0359.68049
[21] Lohrey, M., Decidability and complexity in automatic monoids, Int. J. Found. Comput. Sci., 16, 4, 707-722 (2005) · Zbl 1146.20314
[22] Lohrey, M., Algorithmics on SLP-compressed strings: a survey, Groups Complex. Cryptol., 4, 241-299 (2012) · Zbl 1285.68088
[23] Mazurkiewicz, A., Concurrent program schemes and their interpretations (1977), Aarhus University: Aarhus University Aarhus, DAIMI Rep. PB 78
[24] Miller, C. F., On Group-Theoretic Decision Problems and Their Classification, Annals of Mathematics Studies, vol. 68 (1971), Princeton University Press · Zbl 0277.20054
[25] Miller, C. F., Decision problems for groups - survey and reflections, (Algorithms and Classification in Combinatorial Group Theory (1992), Springer), 1-60 · Zbl 0752.20014
[26] Myasnikov, A.; Roman’kov, V.; Ushakov, A.; Vershik, A., The word and geodesic problems in free solvable groups, Trans. Am. Math. Soc., 362, 4655-4682 (2010) · Zbl 1207.20026
[27] Papadimitriou, Ch., Computation Complexity (1994), Addison-Wesley
[28] Paterson, M.; Razborov, A., The set of minimal braids is co-NP-complete, J. Algorithms, 12, 393-408 (1991) · Zbl 0726.68047
[29] Robinson, D., Parallel algorithms for group word problems (1993), University of California: University of California San Diego, PhD thesis
[30] Sapir, M., Asymptotic invariants, complexity of groups and related problems, Bull. Math. Sci., 1, 2, 277-364 (2011) · Zbl 1293.20041
[31] Serre, J.-P., Trees (1980), Springer, French original 1977
[32] Simon, H.-U., Word problems for groups and contextfree recognition, (Proceedings of Fundamentals of Computation Theory (FCT’79). Proceedings of Fundamentals of Computation Theory (FCT’79), Berlin/Wendisch-Rietz (GDR) (1979), Akademie-Verlag), 417-422
[33] Vollmer, H., Introduction to Circuit Complexity (1999), Springer: Springer Berlin
[34] Waack, S., Tape complexity of word problems, (Gécseg, F., Proceedings of Fundamentals of Computation Theory (FCT’81). Proceedings of Fundamentals of Computation Theory (FCT’81), Lecture Notes in Computer Science, vol. 117 (1981), Springer), 467-471 · Zbl 0498.03038
[35] Wehrfritz, B. A.F., Generalized free products of linear groups, Proc. Lond. Math. Soc., 27, 402-424 (1973) · Zbl 0266.20052
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.