@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. Uniform Characterizations of Nonuniform Complexity Measures, Information and Control, Vol. 67, Nos. 1-3, 1985, pp. 53-69. | MR | Zbl
, and2. Some Comments About Notations of Orders of Magnitude, Buil. EATCS, Vol. 30, 1986, pp. 34-42. | Zbl
and ,3. Bounded-width Polynomial-size Branching Programs Recognize Exactly Those Languages in NCl, In: l8th ACM Symp. Th. of Comp., 1986, pp. 1-5.
,4. On Relating Time and Space to Size and Depth, SIAM J. Comp., Vol. 6. No. 4, 1977, pp. 733-744. | MR | Zbl
,5. 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. Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, No. 3, 1981, pp. 227-246. | MR | Zbl
, , and ,7. About LOG-ON languages, Internal report RR 85/02, Facultat d'Informàtica de Barcelona.
and ,8. Almost context-free languages, Manuscript, 1984.
,9. Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal ACM, Vol. 18, No. 1, 1971, pp. 4-18. | MR | Zbl
,10. On the Separating Power of EOL Systems, RAIRO Inf. Theor., Vol. 17, No. 1, 1983, pp. 13-22. | Numdam | MR | Zbl
and ,11. 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. Straight-line Programs to Compute Finite Languages, Conf. Theor. Comp. Sci., Waterloo, 1977. | MR | Zbl
, and ,13. Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965. | MR | Zbl
,14. On Time Versus Space and Related Problems, Journal ACM, Vol. 2, 1977, pp. 332-337. | MR | Zbl
, and ,15. Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979. | MR | Zbl
and ,16. Some Connections between Nonuniform and Uniform Complexity Classes. In: 12th ACM Symp. Th. of Comp., 1980, pp. 302-309.
and ,17. Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24.
,18. The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20.
,19. Space-bounded Hierarchies and Probabilistic Computations, J. Comp. Syst. Sci., Vol. 28, 1984, pp. 216-230. | MR | Zbl
, and ,20. The Complexity of Computing, Wiley Interscience 1976. | MR | Zbl
,21. The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Informática, Vol. 7, 1976, pp. 95-107. | MR | Zbl
,22. Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Théor. et Appl., (to appear). | Numdam | Zbl
,23. Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19.
and ,24. On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal ACM, Vol. 35, 1988, pp. 461-471. | MR | Zbl
,