On the parallel complexity of linear groups
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 4, pp. 323-354.
@article{ITA_1991__25_4_323_0,
     author = {Waack, St.},
     title = {On the parallel complexity of linear groups},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {323--354},
     publisher = {EDP-Sciences},
     volume = {25},
     number = {4},
     year = {1991},
     mrnumber = {1134386},
     zbl = {0789.68074},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1991__25_4_323_0/}
}
TY  - JOUR
AU  - Waack, St.
TI  - On the parallel complexity of linear groups
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1991
SP  - 323
EP  - 354
VL  - 25
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1991__25_4_323_0/
LA  - en
ID  - ITA_1991__25_4_323_0
ER  - 
%0 Journal Article
%A Waack, St.
%T On the parallel complexity of linear groups
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1991
%P 323-354
%V 25
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1991__25_4_323_0/
%G en
%F ITA_1991__25_4_323_0
Waack, St. On the parallel complexity of linear groups. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991) no. 4, pp. 323-354. http://archive.numdam.org/item/ITA_1991__25_4_323_0/

1. L. Auslander, On a problem of Philip Hall, Ann. of Math., 1967, 86(2), pp. 112-116. | MR | Zbl

2. J. Avenhaus, K. Madlener, Subrekursive Komplexität bei Gruppen, I. Gruppen mit vorgeschriebener Komplexität, Acta Inform., 1977, 9, pp. 87-104. | MR | Zbl

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. | Zbl

4. J. Avenhaus, K. Madlener, The Nielson reduction and P-complete problems in free groups, Theoret. Comput. Sci., 1984, 32, pp. 61-76. | Zbl

5. J. Avenhaus, K. Madlener, On the complexity of intersection and conjugacy problems in free groups, Theoret. Comput. Sci., 1984, pp. 279-295. | Zbl

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. 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. | Zbl

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.

9. S. A. Cook, The classification of problems which have fast parallel algorithms, in: Lecture Notes in Comput. Sci., 158, Springer-Verlag, Berlin, 1983. | MR | Zbl

10. S. A. Cook, A Taxonomy of problems with fast parallel algorithms, Inform. and Control, 1985, 64, pp. 2-22. | MR | Zbl

11. S. A. Cook, P. Mckenzie, Problems complete for deterministic logarithmic space, J. Algorithms, 1987, 8, pp. 385-394. | MR | Zbl

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. | MR | Zbl

13. M. J. Dunwoody, The accessibility of finitely presented groups, Invent. Math., 1985, 81, pp. 449-457. | MR | Zbl

14. M. Hall, Subgroups of finite index in free groups, Canad. J. Math., 1949, 1, pp. 187-190. | MR | Zbl

15.G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, Oxford U. Press, London, 1957. | JFM | Zbl

16. J. E. Hopcroft, J. D. Ullman, Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, 1979. | MR | Zbl

17. M. Krause, S. Waack, On oblivious branching programs of linear length, to appear in Inform. and Comput. | MR | Zbl

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. | Numdam | MR | Zbl

19. S. Lang, Algebra, Addison-Wesley, Reading 1965. | MR | Zbl

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. | MR

21. R. J. Lipton, Y. Zalcstein, Word problems solvable in logspace, J. of the A.C.M., 1977, 24 (3), pp. 322-526. | MR | Zbl

22. W. Magnus, A. Karass, D. Solitar, Combinatorial group theory, Interscience Publishers, 1966. | Zbl

23. A. I. Mal'Cev, On certain classes of infinite solvable groups, Mat. Sb., 1951, 28, pp. 567-598. | MR

24. D. Muller, P. Schupp, Groups, the theory of ends, and context-free languages, J. Comput. System Sci., 1983, 26, pp. 295-310. | MR | Zbl

25. J. E. Savage, The complexity of computing, John Wiley, New York, 1976. | MR | Zbl

26. H. U. Simon, Word problems for groups and contextfree recognition, in: Proc. FCT79, Akademie-Verlag, Berlin, 1979. | MR | Zbl

27. R. G. Swan, Representations of polycyclic groups, Proc. Amer. Math. Soc., 1967, 18, pp. 573-574. | MR | Zbl

28. Tits, Free subgroups in linear groups, J. Algebra, 1972, 20, pp. 250-270. | MR | Zbl

29. C. Tretkoff, Complexity, combinatorial group theory and the language of pulatators, Theoret. Comput. Sci., 56, 1988, pp. 253-275. | MR | Zbl

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. | MR | Zbl

31. S. Waack, Tape complexity of word problems, TR IMATH der AdW der DDR, Berlin 1981. | MR | Zbl

32. S. Waack, Raumkomplexität von Wortproblemen endlicher Gruppenpräsentationen, Dissertation A, Berlin 1983.

33. S. Waack, The parallel complexity of some constructions in combinatorial group theory, J. Inf. Process. Cybern., 1990, 26, 5/6, pp. 265-281. | MR | Zbl

34. I. Wegener, The complexity of boolean functions, Wiley-Teubner Series in Comput. Sci., 1987. | MR | Zbl

35. B. A. F. Wehrfritz, Infinite linear groups, Springer-Verlag, New York, 1973. | MR | Zbl

36. O. Zariski, P. Samuel, Commutative algebra I, II, Van Nostrand, Princton, 1958, 1960. | Zbl