Recursion Theoretic Properties of Frequency Computation and Bounded Queries (Extended Abstract)
作者： Martin Kummer , Frank Stephan
DOI: 10.1007/BFB0022573
关键词:
摘要: The notion of frequency computation captures the class Ω all sets A such that for some n n-fold characteristic function can be computed with less than errors. Alternatively, it by a total oracle machine queries to oracle. We consider recursion theoretic properties special emphasis on r.e. sets.
springer.com
sci-hub.se 参考文章(25)
Richard Beigel, Martin Kummer, Frank Stephan, Quantifying the amount of verboseness (extended abstract) foundations of computer science. pp. 21- 32 ,(1992) , 10.1007/BFB0023860
Richard Beigel, Query-limited reducibilities Stanford University. ,(1988)
Piergiorgio Odifreddi, Classical recursion theory ,(1989)
W. Gasarch, Bounded queries in recursion theory: a survey structure in complexity theory annual conference. pp. 62- 78 ,(1991) , 10.1109/SCT.1991.160245
A N Degtev, REDUCIBILITIES OF TABULAR TYPE IN THE THEORY OF ALGORITHMS Russian Mathematical Surveys. ,vol. 34, pp. 155- 192 ,(1979) , 10.1070/RM1979V034N03ABEH003988
Richard Beigel, William Gasarch, Jim Owings, Nondeterministic bounded query reducibilities Annals of Pure and Applied Logic. ,vol. 41, pp. 107- 118 ,(1989) , 10.1016/0168-0072(89)90010-9
Richard Beigel, William I. Gasarch, Louise Hay, Bounded query classes and the difference hierarchy Archive for Mathematical Logic. ,vol. 29, pp. 69- 84 ,(1989) , 10.1007/BF01620618
Carl G. Jockusch, James C. Owings, Weakly Semirecursive Sets Journal of Symbolic Logic. ,vol. 55, pp. 637- 644 ,(1990) , 10.2307/2274653
R. Beigel, W.I. Gasarch, J. Gill, J.C. Owings, Terse, superterse, and verbose sets Information & Computation. ,vol. 103, pp. 68- 85 ,(1993) , 10.1006/INCO.1993.1014
A. N. Degtev, tt- andm-degrees Algebra and Logic. ,vol. 12, pp. 78- 89 ,(1973) , 10.1007/BF02219290