{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T21:10:18Z","timestamp":1742591418971,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540167617"},{"type":"electronic","value":"9783540398592"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1986]]},"DOI":"10.1007\/3-540-16761-7_49","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T18:50:43Z","timestamp":1330195843000},"page":"1-10","source":"Crossref","is-referenced-by-count":0,"title":["Characterizations of PUNC and precomputation"],"prefix":"10.1007","author":[{"given":"Eric W.","family":"Allender","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","unstructured":"L. Adleman, Two theorems on random polynomial time, Proc. 19th IEEE Symposium on Foundations of Computer Science, pp. 307\u2013311.","DOI":"10.1109\/SFCS.1978.37"},{"key":"1_CR2","unstructured":"E. W. Allender, Invertible functions, Doctoral Dissertation, Georgia Institute of Technology."},{"key":"1_CR3","doi-asserted-by":"crossref","unstructured":"E. W. Allender, The complexity of sparse sets in P, Paper presented at the Structure in Complexity Theory Conference, Berkeley, to appear in Lecture Notes in Computer Science.","DOI":"10.1007\/3-540-16486-3_85"},{"key":"1_CR4","doi-asserted-by":"crossref","unstructured":"J. L. Balcazar, J. Diaz, J. Gabarro, On some \u201cnon-uniform\u201d complexity measures, 5th Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 199, pp. 18\u201327.","DOI":"10.1007\/BFb0028787"},{"key":"1_CR5","doi-asserted-by":"crossref","unstructured":"P. W. Beame, S. A. Cook, and H. J. Hoover, Log depth circuits for division and related problems, Proc. 25th IEEE Symposium on Foundations of Computer Science, pp. 1\u201311.","DOI":"10.1109\/SFCS.1984.715894"},{"key":"1_CR6","doi-asserted-by":"crossref","unstructured":"R. V. Book, Tally languages and complexity classes, Information and Control 26, 186\u2013193.","DOI":"10.1016\/S0019-9958(74)90473-2"},{"key":"1_CR7","doi-asserted-by":"crossref","unstructured":"F.-J. Brandenburg, On one-way auxiliary pushdown automata, Proc. 3rd GI Conference, Lecture Notes in Computer Science 48, pp. 133\u2013144.","DOI":"10.1007\/3-540-08138-0_11"},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"F.-J. Brandenburg, The contextsensitivity of contextsensitive grammars and languages, Proc. 4th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science 52, pp. 272\u2013281.","DOI":"10.1007\/3-540-08342-1_10"},{"key":"1_CR9","doi-asserted-by":"crossref","unstructured":"A. K. Chandra, L. J. Stockmeyer, U. Vishkin, Constant depth reducibility, SIAM J. Comput. 13, 423\u2013439.","DOI":"10.1137\/0213028"},{"key":"1_CR10","doi-asserted-by":"crossref","unstructured":"M. P. Chytil, Comparison of the active visiting and the crossing complexities, Proc. 6th Conference on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science 53, pp. 272\u2013281.","DOI":"10.1007\/3-540-08353-7_145"},{"key":"1_CR11","unstructured":"S. A. Cook, Towards a complexity theory of synchronous parallel computation, L'Enseignement Mathematique 27, 99\u2013124."},{"key":"1_CR12","doi-asserted-by":"crossref","unstructured":"S. A. Cook, The classification of problems which have fast parallel algorithms. Proc. 4th International Conference on Foundations of Computation Theory, Lecture Notes in Computer Science 158, pp. 78\u201393.","DOI":"10.1007\/3-540-12689-9_95"},{"key":"1_CR13","doi-asserted-by":"crossref","unstructured":"P. W. Dymond and S. A. Cook, Hardware complexity and parallel computation, Proc. 20th IEEE Symposium on Foundations of Computer Science, pp. 360\u2013372.","DOI":"10.1109\/SFCS.1980.22"},{"key":"1_CR14","doi-asserted-by":"crossref","unstructured":"J. von zur Gathen, Parallel powering, Proc. 25th Annual ACM Symposium on Theory of Computing, pp. 31\u201336.","DOI":"10.1109\/SFCS.1984.715898"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Z. Galil, Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages, Mathematical Systems Theory 10, 211\u2013228.","DOI":"10.1007\/BF01683273"},{"key":"1_CR16","doi-asserted-by":"crossref","unstructured":"Z. Galil and W. Paul, An efficient general-purpose parallel computer, J. ACM 30, 360\u2013387.","DOI":"10.1145\/322374.322382"},{"key":"1_CR17","doi-asserted-by":"crossref","unstructured":"A. V. Goldberg and M. Sipser, Compression and ranking, Proc. 17th Annual ACM Symposium on Theory of Computing, pp. 440\u2013448.","DOI":"10.1145\/22145.22194"},{"key":"1_CR18","doi-asserted-by":"crossref","unstructured":"L. M. Goldschlager, A universal interconnection pattern for parallel computers, J. ACM 29, 1073\u20131086.","DOI":"10.1145\/322344.322353"},{"key":"1_CR19","doi-asserted-by":"crossref","unstructured":"J. Hartmanis, Generalized Kolmogorov complexity and the structure of feasible computations, Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 439\u2013445.","DOI":"10.1109\/SFCS.1983.21"},{"key":"1_CR20","doi-asserted-by":"crossref","unstructured":"J. Hartmanis and Y. Yesha, Computation times of NP sets of different densities, Theoretical Computer Science 34, 17\u201332.","DOI":"10.1016\/0304-3975(84)90111-7"},{"key":"1_CR21","unstructured":"D. T. Huynh, Non-uniform complexity and the randomness of certain complete languages, Technical Report TR 85\u201334, Computer Science Department, Iowa State University."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"N. D. Jones, Space-bounded reducibility among combinatorial problems, J. Computer and System Sciences 11, 68\u201385.","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"1_CR23","unstructured":"R. M. Karp and R. J. Lipton, Turing machines that take advice, L'Enseignement Mathematique 28, 191\u2013209."},{"key":"1_CR24","doi-asserted-by":"crossref","unstructured":"K. N. King, Measures of parallelism in alternating computation trees, Proc. 13th Annual ACM Symposium on Theory of Computing, pp. 189\u2013201.","DOI":"10.1145\/800076.802472"},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"K.-I. Ko, On the definition of some complexity classes of real numbers, Mathematical Systems Theory 16, 95\u2013109.","DOI":"10.1007\/BF01744572"},{"key":"1_CR26","unstructured":"K.-I. Ko, A definition of infinite pseudorandom sequences, manuscript, University of Houston."},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"N. Pippenger, Pebbling with an auxiliary pushdown, J. Computer and System Sciences 23, 151\u2013165.","DOI":"10.1016\/0022-0000(81)90011-8"},{"key":"1_CR28","unstructured":"C. Rackoff, personal communication."},{"key":"1_CR29","doi-asserted-by":"crossref","unstructured":"W. L. Ruzzo, On uniform circuit complexity, J. Computer and System Sciences 21, 365\u2013383.","DOI":"10.1016\/0022-0000(81)90038-6"},{"key":"1_CR30","unstructured":"W. L. Ruzzo, personal communication."},{"key":"1_CR31","unstructured":"L. J. Stockmeyer, The complexity of decision problems in automata theory and logic, Doctoral Dissertation, M.I.T."},{"key":"1_CR32","doi-asserted-by":"crossref","unstructured":"I. H. Sudborough, Bandwidth constraints on problems complete for polynomial time, Theoretical Computer Science 26, 25\u201352.","DOI":"10.1016\/0304-3975(83)90078-6"},{"key":"1_CR33","unstructured":"U. Vishkin, Synchronous parallel computation \u2014 a survey, preprint, Courant Institute, New York University."},{"key":"1_CR34","doi-asserted-by":"crossref","unstructured":"U. Vishkin, A parallel-design distributed-implementation (PDDI general-purpose computer), Theoretical Computer Science 32, 157\u2013172.","DOI":"10.1016\/0304-3975(84)90028-8"},{"key":"1_CR35","unstructured":"G. Wechsung, The oscillation complexity and a hierarchy of context-free languages, Proc. 2nd Proc. 2nd International Conference on Fundementals of Computation Theory, Akademie-Verlag, Berlin, GDR, pp. 508\u2013515."},{"key":"1_CR36","unstructured":"G. Wechsung, A note on the return complexity, Elektronische Informationsverarbeitung und Kybernetik 16, 139\u2013146."},{"key":"1_CR37","doi-asserted-by":"crossref","unstructured":"G. Wechsung and A. Brandstadt, A relation between space, return and dual return complexities, Theoretical Computer Science 9, 127\u2013140.","DOI":"10.1016\/0304-3975(79)90010-0"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-16761-7_49.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:28:36Z","timestamp":1742588916000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-16761-7_49"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986]]},"ISBN":["9783540167617","9783540398592"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/3-540-16761-7_49","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1986]]}}}