Nonuniform complexity classes specified by lower and upper bounds

 Access to full text

 Full (PDF)

1. 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. Zbl0588.68021MR833860
2. 2. J. L. BALCÁZAR and J. GABARRÓ, Some Comments About Notations of Orders of Magnitude, Buil. EATCS, Vol. 30, 1986, pp. 34-42. Zbl1023.68587
3. 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. 4. A. BORODIN, On Relating Time and Space to Size and Depth, SIAM J. Comp., Vol. 6. No. 4, 1977, pp. 733-744. Zbl0366.68039MR461984
5. 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. Zbl0359.68055MR483712
6. 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. Zbl0469.68081MR619000
7. 7. R. CASAS and J. GABARRO, About LOG-ON languages, Internal report RR 85/02, Facultat d'Informàtica de Barcelona. 
8. 8. M. CHYTIL, Almost context-free languages, Manuscript, 1984. 
9. 9. S. COOK, Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal ACM, Vol. 18, No. 1, 1971, pp. 4-18. Zbl0222.02035MR292605
10. 10. A. EHRENFEUTCH and G. ROZENBERG, On the Separating Power of EOL Systems, RAIRO Inf. Theor., Vol. 17, No. 1, 1983, pp. 13-22. Zbl0512.68059MR701985
11. 11. J. GABARRÓFunciones de complejidad y su relación con las familias abstractas de lenguajes. Ph. D. dissertation, 1983. 
12. 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. Zbl0523.68068MR727660
13. 12. G. GOODRICH, R. LADNER and M. FISCHER, Straight-line Programs to Compute Finite Languages, Conf. Theor. Comp. Sci., Waterloo, 1977. Zbl0409.68025MR502232
14. 13. M. HARRISON, Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965. Zbl0196.51702MR186503
15. 14. J. HOPCROFT, W. PAUL and L. VALIANT, On Time Versus Space and Related Problems, Journal ACM, Vol. 2, 1977, pp. 332-337. Zbl0358.68082MR443428
16. 15. J. HOPCROFT and J. ULLMAN, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979. Zbl0426.68001MR645539
17. 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. 
18. 17. D. KNUTH, Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24. 
19. 18. R. LADNER, The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20. 
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. Zbl0573.68021MR760544
21. 20. J. SAVAGE, The Complexity of Computing, Wiley Interscience 1976. Zbl0391.68025MR495205
22. 21. C. SCHNORR, The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Informática, Vol. 7, 1976, pp. 95-107. Zbl0338.02019MR421889
23. 22. M. J. SERNA, Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Théor. et Appl., (to appear). Zbl0677.68086
24. 23. P. VITANYI and L. MEERTENS, Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19. 
25. 24. I. WEGENER, On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal ACM, Vol. 35, 1988, pp. 461-471. Zbl0652.68063MR935261