{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T14:11:12Z","timestamp":1725459072976},"publisher-location":"Berlin\/Heidelberg","reference-count":15,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540156895"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0028787","type":"book-chapter","created":{"date-parts":[[2006,1,25]],"date-time":"2006-01-25T12:15:07Z","timestamp":1138191307000},"page":"18-27","source":"Crossref","is-referenced-by-count":2,"title":["On some \"non-uniform\" complexity measures"],"prefix":"10.1007","author":[{"given":"J. L.","family":"Balc\u00e1zar","sequence":"first","affiliation":[]},{"given":"J.","family":"D\u00edaz","sequence":"additional","affiliation":[]},{"given":"J.","family":"Gabarr\u00f3","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/BF00289267","volume":"15","author":"S. Aanderaa","year":"1981","unstructured":"S. Aanderaa, E. B\u00f6rger: The equivalence of Horn and network complexity for boolean functions. Acta Informatica 15 (1981), 303\u2013307.","journal-title":"Acta Informatica"},{"key":"3_CR2","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0206023","volume":"6","author":"L. Berman","year":"1977","unstructured":"L. Berman, J. Hartmanis: On isomorphism and density of NP and other complete sets, SIAM J. Comp 6 (1977), 305\u2013322.","journal-title":"SIAM J. Comp"},{"key":"3_CR3","unstructured":"A. Borodin, I. Munro: The computational complexity of algebraic and numeric problems. American Elsivier (1975)."},{"key":"3_CR4","first-page":"132","volume":"48","author":"F. Brandenburg","year":"1977","unstructured":"F. Brandenburg: On one-way auxiliary pushdown automata, 3rd GI conf. Theor. Comp. Sci. (1977), LNCS 48 132\u2013144.","journal-title":"LNCS"},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0304-3975(81)90044-X","volume":"14","author":"W. Bucher","year":"1981","unstructured":"W. Bucher, K. Culik, H. Maurer, D. Wotschke: Concise description of finite languages. TCS 14 (1981), 227\u2013246.","journal-title":"TCS"},{"key":"3_CR6","unstructured":"M. Chytil: Almost context-free languages. Manuscript (1984)."},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"S. Cook: Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18 (1971), 4\u201318.","journal-title":"J. ACM"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"J. Gabarr\u00f3: Initial index: a new complexity function for languages. ICALP 83, 226\u2013236.","DOI":"10.1007\/BFb0036911"},{"key":"3_CR9","unstructured":"G. Goodrich, R. Ladner, M. Fischer: Straight line programs to compute finite languages. Conf. on Theor. Comp. Sci., Waterloo (1977)."},{"key":"3_CR10","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0304-3975(76)90072-4","volume":"1","author":"S. Greibach","year":"1976","unstructured":"S. Greibach: Remarks on the complexity of nondeterministic counter languages. TCS 1 (1976), 269\u2013288.","journal-title":"TCS"},{"issue":"1","key":"3_CR11","first-page":"31","volume":"65","author":"J. Hartmanis","year":"1965","unstructured":"J. Hartmanis, P. Lewis, R. Stearns: Classification of computations by time and memory requirements. Proc. IFIP Cont. 65, 1, 31\u201335 (1965).","journal-title":"Proc. IFIP Cont."},{"key":"3_CR12","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321495.321508","volume":"3","author":"J. Hopcroft","year":"1969","unstructured":"J. Hopcroft, J. Ullman: Some results on tape-bounded Turing machines, J. ACM 3 (1969), 168\u2013177.","journal-title":"J. ACM"},{"key":"3_CR13","first-page":"120","volume":"1","author":"O. Lupanov","year":"1958","unstructured":"O. Lupanov: A method of circuit synthesis, Izv. V.U.Z. Radiof., 1 (1958), 120\u2013140.","journal-title":"Izv. V.U.Z. Radiof."},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1145\/322033.322037","volume":"24","author":"N. Lynch","year":"1977","unstructured":"N. Lynch: Log space recognition and translation of parenthesis languages, J. ACM 24 (1977), 583\u2013590.","journal-title":"J. ACM"},{"key":"3_CR15","unstructured":"J. Savage: The complexity of computing, Wiley Interscience (1976)."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0028787.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T16:58:51Z","timestamp":1607533131000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0028787"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540156895"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/bfb0028787","relation":{},"subject":[]}}