{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:14:09Z","timestamp":1725455649946},"publisher-location":"Berlin\/Heidelberg","reference-count":31,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540571841"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022573","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:14:45Z","timestamp":1131862485000},"page":"243-254","source":"Crossref","is-referenced-by-count":2,"title":["Recursion theoretic properties of frequency computation and bounded queries (extended abstract)"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kummer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","first-page":"864","DOI":"10.2307\/2275436","volume":"57","author":"K. Ambos-Spies","year":"1992","unstructured":"K. Ambos-Spies, A. Nies, R. A. Shore. The theory of the recursively enumerable weak truth-table degrees is undecidable. J. Symb. Logic, 57:864\u2013874, 1992.","journal-title":"J. Symb. Logic"},{"issue":"3","key":"27_CR2","doi-asserted-by":"crossref","first-page":"233","DOI":"10.5802\/aif.938","volume":"33","author":"P. Assouad","year":"1983","unstructured":"P. Assouad. Densit\u00e9 et dimension. Ann. Inst. Fourier, 33(3):233\u2013282, 1983.","journal-title":"Ann. Inst. Fourier"},{"key":"27_CR3","volume-title":"Ph.D. thesis","author":"R. Beigel","year":"1987","unstructured":"R. Beigel. Query-limited reducibilities. Ph.D. thesis, Stanford University, Stanford, USA, 1987."},{"key":"27_CR4","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1006\/inco.1993.1014","volume":"103","author":"R. Beigel","year":"1993","unstructured":"R. Beigel, W. I. Gasarch, J. Gill, J. C. Owings, Jr. Terse, superterse, and verbose sets. Information and Computation, 103:68\u201385, 1993.","journal-title":"Information and Computation"},{"key":"27_CR5","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/BFb0023860","volume":"620","author":"R. Beigel","year":"1992","unstructured":"R. Beigel, M. Kummer, F. Stephan. Quantifying the amount of verboseness. To appear in: Information and Computation (a preliminary version appeared in: Lecture Notes for Computer Science (\u201cLogic at Tver\u201d), Vol.620, pp. 21\u201332, 1992).","journal-title":"Lecture Notes for Computer Science (\u201cLogic at Tver\u201d)"},{"key":"27_CR6","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1007\/BF01620618","volume":"29","author":"R. Beigel","year":"1989","unstructured":"R. Beigel, W. I. Gasarch, L. Hay. Bounded query classes and the difference hierarchy. Arch. Math. Logic, 29:69\u201384, 1989.","journal-title":"Arch. Math. Logic"},{"key":"27_CR7","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0168-0072(89)90010-9","volume":"41","author":"R. Beigel","year":"1989","unstructured":"R. Beigel, W. I. Gasarch, J. C. Owings, Jr. Nondeterministic bounded query reducibilities. Annals of Pure and Applied Logic, 41:107\u2013118, 1989.","journal-title":"Annals of Pure and Applied Logic"},{"key":"27_CR8","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, M. K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. J. of the ACM, 36:929\u2013965, 1989.","journal-title":"J. of the ACM"},{"key":"27_CR9","doi-asserted-by":"crossref","unstructured":"V. K. Bulitko. Reducibility by Zhegalkin linear tables. Sib. Math. J., 21:332\u2013339.","DOI":"10.1007\/BF00968176"},{"key":"27_CR10","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1007\/BF02219729","volume":"10","author":"A. N. Degtev","year":"1971","unstructured":"A. N. Degtev. Hypersimple sets with retraceable complements. Algebra and Logic, 10:235\u2013246, 1971.","journal-title":"Algebra and Logic"},{"key":"27_CR11","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/BF02219290","volume":"12","author":"A. N. Degtev","year":"1973","unstructured":"A. N. Degtev. tt- and m-degrees. Algebra and Logic, 12:78\u201389, 1973.","journal-title":"Algebra and Logic"},{"issue":"3","key":"27_CR12","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1070\/RM1979v034n03ABEH003988","volume":"34","author":"A. N. Degtev","year":"1979","unstructured":"A. N. Degtev. Reducibilities of tabular type in the theory of algorithms. Russian Math. Surveys, 34(3):155\u2013192, 1979.","journal-title":"Russian Math. Surveys"},{"key":"27_CR13","unstructured":"A. N. Degtev. On (m,n)-computable sets. In Algebraic Systems (Edited by D.I. Moldavanskij). Ivanova Gos. Univ. 88\u201399, 1981. (Russian) (MR 86b:03049)"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"W. I. Gasarch. Bounded queries in recursion theory: a survey. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference. IEEE Computer Society Press, 62\u201378, 1991.","DOI":"10.1109\/SCT.1991.160245"},{"key":"27_CR15","doi-asserted-by":"crossref","first-page":"677","DOI":"10.2307\/2275300","volume":"57","author":"V. Harizanov","year":"1992","unstructured":"V. Harizanov, M. Kummer, J. C. Owings, Jr. Frequency computation and the cardinality theorem. J. Symb. Log., 57:677\u2013681, 1992.","journal-title":"J. Symb. Log."},{"key":"27_CR16","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler, E. Welzl. \u03b5-nets and simplex range queries. Discrete Comput. Geom., 2:127\u2013151, 1987.","journal-title":"Discrete Comput. Geom."},{"key":"27_CR17","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1090\/S0002-9947-1968-0220595-7","volume":"131","author":"C. G. Jockusch Jr.","year":"1968","unstructured":"C. G. Jockusch, Jr. Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc., 131:420\u2013436, 1968.","journal-title":"Trans. Amer. Math. Soc."},{"key":"27_CR18","first-page":"83","volume-title":"Lecture Notes in Mathematics, Vol. 859","author":"C. G. Jockusch Jr.","year":"1981","unstructured":"C. G. Jockusch, Jr. Three easy constructions of recursively enumerable degrees. In Lecture Notes in Mathematics, Vol. 859, 83\u201391, Springer-Verlag, Berlin, 1981."},{"key":"27_CR19","doi-asserted-by":"crossref","first-page":"637","DOI":"10.2307\/2274653","volume":"55","author":"C. G. Jockusch Jr.","year":"1990","unstructured":"C. G. Jockusch, Jr., J. C. Owings, Jr. Weakly semirecursive sets. J. Symb. Log., 55:637\u2013644, 1990.","journal-title":"J. Symb. Log."},{"key":"27_CR20","first-page":"873","volume":"13","author":"E. B. Kinber","year":"1972","unstructured":"E. B. Kinber. On frequency calculations of general recursive predicates. Sov. Math. Dokl., 13:873\u2013876, 1972.","journal-title":"Sov. Math. Dokl."},{"key":"27_CR21","first-page":"179","volume":"2","author":"E. B. Kinber","year":"1976","unstructured":"E. B. Kinber. Frequency computations in finite automata. Cybernetics, 2:179\u2013187, 1976.","journal-title":"Cybernetics"},{"key":"27_CR22","doi-asserted-by":"crossref","first-page":"682","DOI":"10.2307\/2275299","volume":"57","author":"M. Kummer","year":"1992","unstructured":"M. Kummer. A proof of Beigel's cardinality conjecture. J. Symb. Log., 57:682\u2013687, 1992.","journal-title":"J. Symb. Log."},{"key":"27_CR23","unstructured":"M. Kummer, F. Stephan. Some aspects of frequency computation. Technical Report Nr. 21\/91, Fakult\u00e4t f\u00fcr Informatik, Universit\u00e4t Karlsruhe, 1991."},{"key":"27_CR24","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1090\/S0002-9939-1976-0416880-6","volume":"60","author":"P. H. Morris","year":"1976","unstructured":"P. H. Morris. A reducibility condition for recursiveness. Proceedings of the American Math. Soc., 60:270\u2013272, 1976.","journal-title":"Proceedings of the American Math. Soc."},{"key":"27_CR25","volume-title":"Classical Recursion Theory","author":"P. Odifreddi","year":"1989","unstructured":"P. Odifreddi. Classical Recursion Theory. North-Holland, Amsterdam, 1989."},{"key":"27_CR26","unstructured":"G. F. Rose. An extended notion of computability. In Abstr. Intern. Congr. for Logic, Meth., and Phil. of Science, Stanford, California, 1960."},{"key":"27_CR27","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"R. I. Soare","year":"1987","unstructured":"R. I. Soare. Recursively Enumerable Sets and Degrees. Springer-Verlag, Berlin, 1987."},{"key":"27_CR28","first-page":"25","volume":"2","author":"B. A. Trakhtenbrot","year":"1963","unstructured":"B. A. Trakhtenbrot. On frequency computation of functions. Algebra i Logika, 2:25\u201332, 1963. (Russian)","journal-title":"Algebra i Logika"},{"key":"27_CR29","first-page":"814","volume":"11","author":"B. A. Trakhtenbrot","year":"1970","unstructured":"B. A. Trakhtenbrot. On autoreducibility. Sov. Math. Dokl., 11:814\u2013817, 1970.","journal-title":"Sov. Math. Dokl."},{"key":"27_CR30","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"V. N. Vapnik, A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl., 16:264\u2013280, 1971.","journal-title":"Theory Probab. Appl."},{"key":"27_CR31","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1002\/malq.19620080313","volume":"8","author":"C. E. M. Yates","year":"1962","unstructured":"C. E. M. Yates. Recursively enumerable sets and retracing functions. Zeit. Math. Log. Grund. Math., 8:331\u2013345, 1962.","journal-title":"Zeit. Math. Log. Grund. Math."}],"container-title":["Lecture Notes in Computer Science","Computational Logic and Proof Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0022573.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:49:07Z","timestamp":1607550547000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022573"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540571841"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/bfb0022573","relation":{},"subject":[]}}