On the parallel complexity of linear groups
Waack, St.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 25 (1991), p. 323-354 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1991-01-01
@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},
     volume = {25},
     year = {1991},
     pages = {323-354},
     mrnumber = {1134386},
     zbl = {0789.68074},
     language = {en},
     url = {http://dml.mathdoc.fr/item/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) pp. 323-354. http://gdmltest.u-ga.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. | MR 218454 | Zbl 0149.26904

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

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 0371.02020

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

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

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 0619.68047

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 734711 | Zbl 0529.68014

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

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

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 908875 | Zbl 0647.68045

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

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

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

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

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

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 984586 | Zbl 0664.68046

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

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 468316

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

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

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

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

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

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

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

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

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

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 653014 | Zbl 0498.03038

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

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 1072920 | Zbl 0698.68053

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

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

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