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

Voir la notice de l'article provenant de la source Numdam

@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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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. | Zbl | MR

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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