Complete problems for symmetric logspace involving free groups. (English) Zbl 0743.68064

Stewart, Iain A.

Inf. Process. Lett. 40, No. 5, 263-267 (1991).

Summary: We show that the Generalized Word Problem for finitely-generated subgroups of Countably-generated free groups with generators of length 2, GWPC(2), is complete for NSYMLOG via logspace reductions. We use N. Immerman’s logical characterization of NSYMLOG as \((FO+\hbox{pos}STC)\), in [SIAM J. Comput. 16, 760-778 (1987; Zbl 0634.68034)].

MSC:

68Q15	Complexity classes (hierarchies, relations among complexity classes, etc.)
20F05	Generators, relations, and presentations of groups
20F10	Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

Keywords:

complete problems; symmetric logspace; finite model theory; Generalized Word Problem; free groups

Citations:

Zbl 0634.68034

References:

[1]	Avenhaus, J.; Madlener, K., The Nielsen reduction and P-complete problems in free groups, Theoret. comput. sci., 32, 61-76, (1984) · Zbl 0555.20015
[2]	Immerman, N., Languages that capture complexity classes, SIAM J. comput., 16, 4, 760-778, (1987) · Zbl 0634.68034
[3]	Lewis, H.R.; Papadimitriou, C.H., Symmetric space bounded computation, Theoret. comput. sci., 19, 161-187, (1982) · Zbl 0491.68045
[4]	Lipton, R.J.; Zalcstein, Y., Word problems solvable in logspace, J. ACM, 24, 3, 522-526, (1977) · Zbl 0359.68049
[5]	Lyndon, R.C.; Schupp, P.E., Combinatorial group theory, (1977), Springer New York · Zbl 0368.20023
[6]	Magnus, W.; Karrass, A.; Solitar, D., Combinatorial group theory, (1976), Dover New York
[7]	Reif, J., Symmetric complementation, J. ACM, 31, 2, 401-421, (1984) · Zbl 0632.68062
[8]	Rotman, J.J., An introduction to the theory of groups, (1984), Allyn & Bacon Newton, MA · Zbl 0576.20001