Generality’s Price

1. Barzdin, J.A.: Two theorems on the limiting synthesis of functions. In: Theory of Algorithms and Programs, Latvian State University, Riga, U.S.S.R, vol. 210, pp. 82–88 (1974)

   Google Scholar 

2. Blum, L., Blum, M.: Toward a mathematical theory of inductive inference. Information and Control 28, 125–155 (1975)

   Article  MATH  MathSciNet  Google Scholar 

3. Blum, M.: A machine independent theory of the complexity of recursive functions. Journal of the ACM 14, 322–336 (1967)

   Article  MATH  Google Scholar 

4. Case, J., Chen, K., Jain, S.: Costs of general purpose learning. Theoretical Computer Science 259, 455–473 (2001)

   Article  MATH  MathSciNet  Google Scholar 

5. Chen, K.: Tradeoffs in machine inductive inference, Ph.D. thesis, SUNY at Buffalo (1981)

   Google Scholar 

6. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to algorithms, 2nd edn. MIT Press, Cambridge (2001)

   MATH  Google Scholar 

7. Chew, P., Machtey, M.: A note on structure and looking back applied to the relative complexity of computable functions. Journal of Computer and System Sciences 22, 53–59 (1981)

   Article  MATH  MathSciNet  Google Scholar 

8. Case, J., Smith, C.: Comparison of identification criteria for machine inductive inference. Theoretical Computer Science 25, 193–220 (1983)

   Article  MATH  MathSciNet  Google Scholar 

9. Gold, E.M.: Language identification in the limit. Information and Control 10, 447–474 (1967)

   Article  MATH  Google Scholar 

10. Hartmanis, J., Stearns, R.: On the computational complexity of algorithms. Transactions of the American Mathematical Society 117, 285–306 (1965)

    Article  MATH  MathSciNet  Google Scholar 

11. Hopcroft, J., Ullman, J.: Introduction to automata theory languages and computation. Addison-Wesley Publishing Company, Reading (1979)

    MATH  Google Scholar 

12. Jones, N.: Computability and complexity from a programming perspective. MIT Press, Cambridge (1997)

    MATH  Google Scholar 

13. Jain, S., Osherson, D., Royer, J., Sharma, A.: Systems that learn: An introduction to learning theory, 2nd edn. MIT Press, Cambridge (1999)

    Google Scholar 

14. Ladner, R.: On the structure of polynomial time reducibility. Journal of the ACM 22, 155–171 (1975)

    Article  MATH  MathSciNet  Google Scholar 

15. Landweber, L., Lipton, R., Robertson, E.: On the structure of sets in NP and other complexity classes. Theoretical Computer Science 15, 181–200 (1981)

    Article  MATH  MathSciNet  Google Scholar 

16. Li, M., Vitányi, P.: An introduction to Kolmogorov complexity and its applications, 2nd edn. Springer, Heidelberg (1997)

    MATH  Google Scholar 

17. Mendelson, E.: Introduction to mathematical logic, 4th edn. Chapman & Hall, London (1997)

    MATH  Google Scholar 

18. Royer, J., Case, J.: Subrecursive programming systems: Complexity & succinctness. Birkhäuser, Basel (1994)

    MATH  Google Scholar 

19. Regan, K.: The topology of provability in complexity theory. Journal of Computer and System Sciences 36, 384–432 (1988)

    Article  MathSciNet  Google Scholar 

20. Rogers, H.: Theory of recursive functions and effective computability. Mc- Graw Hill, New York (1967); Reprinted MIT Press, Cambridge (1987)

    Google Scholar 

21. Schoning, U.: A uniform approach to obtain diagonal sets in complexity classes. Theoretical Computer Science 18, 95–103 (1982)

    Article  MathSciNet  Google Scholar 

22. Schmidt, D.: The recursion-theoretic structure of complexity classes. Theoretical Computer Science 38, 143–156 (1985)

    Article  MATH  MathSciNet  Google Scholar 

Download references