{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,28]],"date-time":"2026-01-28T18:43:19Z","timestamp":1769625799396,"version":"3.49.0"},"reference-count":25,"publisher":"EDP Sciences","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Theor. Inf. Appl."],"published-print":{"date-parts":[[1989]]},"DOI":"10.1051\/ita\/1989230201771","type":"journal-article","created":{"date-parts":[[2017,2,2]],"date-time":"2017-02-02T15:18:45Z","timestamp":1486048725000},"page":"177-194","source":"Crossref","is-referenced-by-count":2,"title":["Nonuniform complexity classes specified by lower and upper bounds"],"prefix":"10.1051","volume":"23","author":[{"given":"Jos\u00e9 L.","family":"Balc\u00e1zar","sequence":"first","affiliation":[]},{"given":"Joaquim","family":"Gabarr\u00f3","sequence":"additional","affiliation":[]}],"member":"250","published-online":{"date-parts":[[2011,1,8]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"1. BALC\u00c1ZAR J. L., D\u00cdAZ J. and GABARR\u00d3 J. Uniform Characterizations of Nonuniform Complexity Measures, Information and Control, Vol. 67, Nos. 1-3, 1985, pp. 53-69.8338600588.68021","DOI":"10.1016\/S0019-9958(85)80026-7"},{"key":"R2","unstructured":"2. BALC\u00c1ZAR J. L. and GABARR\u00d3 J., Some Comments About Notations of Orders of Magnitude, Buil. EATCS, Vol. 30, 1986, pp. 34-42.1023.68587"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"3. BARRINGTON D., Bounded-width Polynomial-size Branching Programs Recognize Exactly Those Languages in NCl, In: l8th ACM Symp. Th. of Comp., 1986, pp. 1-5.","DOI":"10.1145\/12130.12131"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"4. BORODIN A., On Relating Time and Space to Size and Depth, SIAM J. Comp., Vol. 6. No. 4, 1977, pp. 733-744.4619840366.68039","DOI":"10.1137\/0206054"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"5. BRANDENBURG F., 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.4837120359.68055","DOI":"10.1007\/3-540-08138-0_11"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"6. BUCHER W., CULIK K., MAURER H. and WOTSCHKE D., Concise Description of Finite Languages, Theor. Comp. Sci., Vol. 14, No. 3, 1981, pp. 227-246.6190000469.68081","DOI":"10.1016\/0304-3975(81)90044-X"},{"key":"R7","unstructured":"7. CASAS R. and GABARRO J., About LOG-ON languages, Internal report RR 85\/02, Facultat d'Inform\u00e0tica de Barcelona."},{"key":"R8","unstructured":"8. CHYTIL M., Almost context-free languages, Manuscript, 1984."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"9. COOK S., Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, Journal ACM, Vol. 18, No. 1, 1971, pp. 4-18.2926050222.02035","DOI":"10.1145\/321623.321625"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"10. EHRENFEUTCH A. and ROZENBERG G., On the Separating Power of EOL Systems, RAIRO Inf. Theor., Vol. 17, No. 1, 1983, pp. 13-22.921747019850512.68059","DOI":"10.1051\/ita\/1983170100131"},{"key":"R11","unstructured":"11. GABARR\u00d3 J. Funciones de complejidad y su relaci\u00f3n con las familias abstractas de lenguajes. Ph. D. dissertation, 1983."},{"key":"R12","unstructured":"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.7276600523.68068"},{"key":"R13","unstructured":"12. GOODRICH G., LADNER R. and FISCHER M., Straight-line Programs to Compute Finite Languages, Conf. Theor. Comp. Sci., Waterloo, 1977.5022320409.68025"},{"key":"R14","unstructured":"13. HARRISON M., Introduction to Switching and Automata Theory, McGraw Hill, New York, 1965.1865030196.51702"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"14. HOPCROFT J., PAUL W. and VALIANT L., On Time Versus Space and Related Problems, Journal ACM, Vol. 2, 1977, pp. 332-337.4434280358.68082","DOI":"10.1145\/322003.322015"},{"key":"R16","unstructured":"15. HOPCROFT J. and ULLMAN J., Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading (Mass.), 1979.6455390426.68001"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"16. KARP R. and LIPTON R., Some Connections between Nonuniform and Uniform Complexity Classes. In: 12th ACM Symp. Th. of Comp., 1980, pp. 302-309.","DOI":"10.1145\/800141.804678"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"17. KNUTH D., Big Omicron and Big Omega and Big Theta, SIGACT News, Apr.-June 1976, pp. 18-24.","DOI":"10.1145\/1008328.1008329"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"18. LADNER R., The Circuit Value Problem is Log Space Completefor P, SIGACT News, January 1975, pp. 18-20.","DOI":"10.1145\/990518.990519"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"19. Ruzzo W., SIMON J. and TOMPA M., Space-bounded Hierarchies and Probabilistic Computations, J. Comp. Syst. Sci., Vol. 28, 1984, pp. 216-230.7605440573.68021","DOI":"10.1016\/0022-0000(84)90066-7"},{"key":"R21","unstructured":"20. SAVAGE J., The Complexity of Computing, Wiley Interscience 1976.4952050391.68025"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"21. SCHNORR C., The Network Complexity and the Turing Machine Complexity of Finite Functions, Acta Inform\u00e1tica, Vol. 7, 1976, pp. 95-107.4218890338.02019","DOI":"10.1007\/BF00265223"},{"key":"R23","unstructured":"22. SERNA M. J., Asymptotical Behaviour of Some Non-Uniform Measures, Inf. Th\u00e9or. et Appl., (to appear).923350677.68086"},{"key":"R24","unstructured":"23. VITANYI P. and MEERTENS L., Big Omega Versus the Wild Functions, Bull. EATCS, 22 Feb. 1984, pp. 14-19."},{"key":"R25","doi-asserted-by":"crossref","unstructured":"24. WEGENER I., On the Complexity of Branching Programs and Decision Trees for Clique Functions, Journal ACM, Vol. 35, 1988, pp. 461-471.9352610652.68063","DOI":"10.1145\/42282.46161"}],"container-title":["RAIRO - Theoretical Informatics and Applications"],"original-title":[],"link":[{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1989230201771\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T06:02:08Z","timestamp":1568786528000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rairo-ita.org\/10.1051\/ita\/1989230201771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989]]},"references-count":25,"journal-issue":{"issue":"2"},"alternative-id":["ita1989230201771"],"URL":"https:\/\/doi.org\/10.1051\/ita\/1989230201771","relation":{},"ISSN":["0988-3754","1290-385X"],"issn-type":[{"value":"0988-3754","type":"print"},{"value":"1290-385X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989]]}}}