Nonuniform complexity classes specified by lower and upper bounds
Balcázar, José L. ; Gabarró, Joaquim
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989), p. 177-194 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1989-01-01
@article{ITA_1989__23_2_177_0,
     author = {Balc\'azar, Jos\'e L. and Gabarr\'o, Joaquim},
     title = {Nonuniform complexity classes specified by lower and upper bounds},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {23},
     year = {1989},
     pages = {177-194},
     mrnumber = {1001725},
     zbl = {0681.68054},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1989__23_2_177_0}
}

Balcázar, José L.; Gabarró, Joaquim. Nonuniform complexity classes specified by lower and upper bounds. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) pp. 177-194. http://gdmltest.u-ga.fr/item/ITA_1989__23_2_177_0/

1. J. L. Balcázar, J. Díaz and J. Gabarró Uniform Characterizations of Nonuniform Complexity Measures, Information and Control, Vol. 67, Nos. 1-3, 1985, pp. 53-69. | MR 833860 | Zbl 0588.68021

2. J. L. Balcázar and J. Gabarró, Some Comments About Notations of Orders of Magnitude, Buil. EATCS, Vol. 30, 1986, pp. 34-42. | Zbl 1023.68587

3. D. Barrington, Bounded-width Polynomial-size Branching Programs Recognize Exactly Those Languages in NCl, In: l8th ACM Symp. Th. of Comp., 1986, pp. 1-5.

4. A. Borodin, On Relating Time and Space to Size and Depth, SIAM J. Comp., Vol. 6. No. 4, 1977, pp. 733-744. | MR 461984 | Zbl 0366.68039

5. F. Brandenburg, On One-way Auxiliary Pushdown Automata, In: 3rd GI Conf. on Theor. Comp. Sci., 1977, Springer Verlag, Lect. Notes in Comp. Sci., Vol. 48, pp. 132-144. | MR 483712 | Zbl 0359.68055

6. W. Bucher, K. Culik, H. Maurer and D. Wotschke, Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, No. 3, 1981, pp. 227-246. | MR 619000 | Zbl 0469.68081

7. R. Casas and J. Gabarro, About LOG-ON languages, Internal report RR 85/02, Facultat d'Informàtica de Barcelona.

8. M. Chytil, Almost context-free languages, Manuscript, 1984.

9. S. Cook, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal ACM, Vol. 18, No. 1, 1971, pp. 4-18. | MR 292605 | Zbl 0222.02035

10. A. Ehrenfeutch and G. Rozenberg, On the Separating Power of EOL Systems, RAIRO Inf. Theor., Vol. 17, No. 1, 1983, pp. 13-22. | Numdam | MR 701985 | Zbl 0512.68059

11. J. Gabarró Funciones de complejidad y su relación con las familias abstractas de lenguajes. Ph. D. dissertation, 1983.

See also: Initial Index: a new Complexity Function for Languages, In: 10th Int. Coll. on Aut. Lang. and Prog., 1983, Springer Verlag, Lect. Notes in Comp. Sci., Vol. 154, pp. 226-236. | MR 727660 | Zbl 0523.68068

12. G. Goodrich, R. Ladner and M. Fischer, Straight-line Programs to Compute Finite Languages, Conf. Theor. Comp. Sci., Waterloo, 1977. | MR 502232 | Zbl 0409.68025

13. M. Harrison, Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965. | MR 186503 | Zbl 0196.51702

14. J. Hopcroft, W. Paul and L. Valiant, On Time Versus Space and Related Problems, Journal ACM, Vol. 2, 1977, pp. 332-337. | MR 443428 | Zbl 0358.68082

15. J. Hopcroft and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979. | MR 645539 | Zbl 0426.68001

16. R. Karp and R. Lipton, Some Connections between Nonuniform and Uniform Complexity Classes. In: 12th ACM Symp. Th. of Comp., 1980, pp. 302-309.

17. D. Knuth, Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24.

18. R. Ladner, The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20.

19. W. Ruzzo, J. Simon and M. Tompa, Space-bounded Hierarchies and Probabilistic Computations, J. Comp. Syst. Sci., Vol. 28, 1984, pp. 216-230. | MR 760544 | Zbl 0573.68021

20. J. Savage, The Complexity of Computing, Wiley Interscience 1976. | MR 495205 | Zbl 0391.68025

21. C. Schnorr, The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Informática, Vol. 7, 1976, pp. 95-107. | MR 421889 | Zbl 0338.02019

22. M. J. Serna, Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Théor. et Appl., (to appear). | Numdam | Zbl 0677.68086

23. P. Vitanyi and L. Meertens, Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19.

24. I. Wegener, On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal ACM, Vol. 35, 1988, pp. 461-471. | MR 935261 | Zbl 0652.68063