On the parallel complexity of linear groups

 Access to full text

 Full (PDF)

1. 1. L. AUSLANDER, On a problem of Philip Hall, Ann. of Math., 1967, 86(2), pp. 112-116. Zbl0149.26904MR218454
2. 2. J. AVENHAUS, K. MADLENER, Subrekursive Komplexität bei Gruppen, I. Gruppen mit vorgeschriebener Komplexität, Acta Inform., 1977, 9, pp. 87-104. Zbl0371.02019MR498062
3. 3. J. AVENHAUS, K. MADLENER, Subrekursive Komplexität bei Gruppen, II. Der Einbettungssatz von Higman für entscheidbare Gruppen, Acta Inform., 1978, 9, pp. 183-193. Zbl0371.02020
4. 4. J. AVENHAUS, K. MADLENER, The Nielson reduction and P-complete problems in free groups, Theoret. Comput. Sci., 1984, 32, pp. 61-76. Zbl0555.20015
5. 5. J. AVENHAUS, K. MADLENER, On the complexity of intersection and conjugacy problems in free groups, Theoret. Comput. Sci., 1984, pp. 279-295. Zbl0555.20016
6. 6. D. A. BARRINGTON, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, in: Proc. 18th A.C.M. S.T.O.C., 1986, pp. 1-5. 
7. 7. P. W. BEAME, S. A. COOK, H. J. HOOVER, Logdepth circuits for division and related problems, S.I.A.M. J. Comput., 1986, 15 (4), pp. 993-1003. Zbl0619.68047
8. 8. A. BORODIN, S. A. COOK, N. PIPPENGER, Parallel computation for well-endowed rings and space bounded probabilistic machines, TR # 162/83, University of Toronto. Zbl0598.68043
9. 9. S. A. COOK, The classification of problems which have fast parallel algorithms, in: Lecture Notes in Comput. Sci., 158, Springer-Verlag, Berlin, 1983. Zbl0529.68014MR734711
10. 10. S. A. COOK, A Taxonomy of problems with fast parallel algorithms, Inform. and Control, 1985, 64, pp. 2-22. Zbl0575.68045MR837088
11. 11. S. A. COOK, P. MCKENZIE, Problems complete for deterministic logarithmic space, J. Algorithms, 1987, 8, pp. 385-394. Zbl0644.68058MR905994
12. 12. S. A. COOK, P. MCKENZIE, The parallel complexity of abelian permutation group problems, S.I.A.M. J. Comput., 1987, 16(2), pp. 880-909. Zbl0647.68045MR908875
13. 13. M. J. DUNWOODY, The accessibility of finitely presented groups, Invent. Math., 1985, 81, pp. 449-457. Zbl0572.20025MR807066
14. 14. M. HALL, Subgroups of finite index in free groups, Canad. J. Math., 1949, 1, pp. 187-190. Zbl0031.34001MR28836
15. 15. G. H. HARDY, E. M. WRIGHT, An introduction to the theory of numbers, Oxford U. Press, London, 1957. Zbl0058.03301JFM64.0093.03
16. 16. J. E. HOPCROFT, J. D. ULLMAN, Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, 1979. Zbl0426.68001MR645539
17. 17. M. KRAUSE, S. WAACK, On oblivious branching programs of linear length, to appear in Inform. and Comput. Zbl0727.68038MR1127534
18. 18. K. KRIEGEL, S. WAACK, Lower bounds on the complexity of real-time branching programs, RAIRO Inform. Théor. Appl., 1988, 22 (4), pp. 447-459. Zbl0664.68046MR984586
19. 19. S. LANG, Algebra, Addison-Wesley, Reading 1965. Zbl0193.34701MR197234
20. 20. R. J. LIPTON, Polynomials with 0-1 coefficients that are hard to evaluate, in: Proc. 16th Ann. I.E.E.E. Symp. on Foundations of Comp. Sci., 1975, pp. 6-10. MR468316
21. 21. R. J. LIPTON, Y. ZALCSTEIN, Word problems solvable in logspace, J. of the A.C.M., 1977, 24 (3), pp. 322-526. Zbl0359.68049MR445901
22. 22. W. MAGNUS, A. KARASS, D. SOLITAR, Combinatorial group theory, Interscience Publishers, 1966. Zbl0138.25604
23. 23. A. I. MAL'CEV, On certain classes of infinite solvable groups, Mat. Sb., 1951, 28, pp. 567-598. MR43088
24. 24. D. MULLER, P. SCHUPP, Groups, the theory of ends, and context-free languages, J. Comput. System Sci., 1983, 26, pp. 295-310. Zbl0537.20011MR710250
25. 25. J. E. SAVAGE, The complexity of computing, John Wiley, New York, 1976. Zbl0391.68025MR495205
26. 26. H. U. SIMON, Word problems for groups and contextfree recognition, in: Proc. FCT79, Akademie-Verlag, Berlin, 1979. Zbl0413.68044MR563704
27. 27. R. G. SWAN, Representations of polycyclic groups, Proc. Amer. Math. Soc., 1967, 18, pp. 573-574. Zbl0153.03801MR213442
28. 28. TITS, Free subgroups in linear groups, J. Algebra, 1972, 20, pp. 250-270. Zbl0236.20032MR286898
29. 29. C. TRETKOFF, Complexity, combinatorial group theory and the language of pulatators, Theoret. Comput. Sci., 56, 1988, pp. 253-275. Zbl0649.20032MR946201
30. 30. S. WAACK, Tape complexity of word problems, in: Proc. FCT'81, Lecture Notes in Comput. Sci., 1981, 117, Springer-Verlag, Berlin, pp. 467-471. Zbl0498.03038MR653014
31. 31. S. WAACK, Tape complexity of word problems, TR IMATH der AdW der DDR, Berlin 1981. Zbl0468.03021MR644148
32. 32. S. WAACK, Raumkomplexität von Wortproblemen endlicher Gruppenpräsentationen, Dissertation A, Berlin 1983. 
33. 33. S. WAACK, The parallel complexity of some constructions in combinatorial group theory, J. Inf. Process. Cybern., 1990, 26, 5/6, pp. 265-281. Zbl0698.68053MR1072920
34. 34. I. WEGENER, The complexity of boolean functions, Wiley-Teubner Series in Comput. Sci., 1987. Zbl0623.94018MR905473
35. 35. B. A. F. WEHRFRITZ, Infinite linear groups, Springer-Verlag, New York, 1973. Zbl0261.20038MR335656
36. 36. O. ZARISKI, P. SAMUEL, Commutative algebra I, II, Van Nostrand, Princton, 1958, 1960. Zbl0081.26501