Nonuniform complexity classes specified by lower and upper bounds
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 23 (1989) no. 2, pp. 177-194. 
@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},
     pages = {177--194},
     publisher = {EDP-Sciences},
     volume = {23},
     number = {2},
     year = {1989},
     mrnumber = {1001725},
     zbl = {0681.68054},
     language = {en},
     url = {http://www.numdam.org/item/ITA_1989__23_2_177_0/}
}
TY  - JOUR
AU  - Balcázar, José L.
AU  - Gabarró, Joaquim
TI  - Nonuniform complexity classes specified by lower and upper bounds
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1989
SP  - 177
EP  - 194
VL  - 23
IS  - 2
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_1989__23_2_177_0/
LA  - en
ID  - ITA_1989__23_2_177_0
ER  - 
%0 Journal Article
%A Balcázar, José L.
%A Gabarró, Joaquim
%T Nonuniform complexity classes specified by lower and upper bounds
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1989
%P 177-194
%V 23
%N 2
%I EDP-Sciences
%U http://www.numdam.org/item/ITA_1989__23_2_177_0/
%G en
%F 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) no. 2, pp. 177-194. http://www.numdam.org/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 | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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