Craig's interpolation theorem, in computation theory

 Access to full text

 Full (PDF)

 Full (DjVu)

1. Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1974) - The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass.. Zbl0326.68005
2. Bell, J.L., Machover, M. (1977) - A course in mathematical logic, North-Holland, Amsterdam. Zbl0359.02001
3. Cook, S.A. (1971) - The complexity of theorem proving procedures, «Proc. Third ACM Symposium», 151-158. 
4. Cook, S.A. and Rechkow, R.A. (1979) - The relative efficiency of propositional proof systems, «J. Symb. Logic», 44.1, 36-50. Zbl0408.03044
5. Craig, W. (1957) - Linear reasoning. A new form of the Herbrand-Gentzen theorem, «J. Symb. Logic», 22, 250-268. Zbl0081.24402
6. Feferman, S. (1974) - Two notes on abstract model theory, I, «Fund. Math.», 82, 153-165, and II, ibid. 89 (1975) 111-130. Zbl0296.02026
7. Monk, J.D. (1976) - Mathematical Logic, Springer-Verlag, Berlin. Zbl0354.02002MR465767
8. Mundici, D. (1981) - Robinson's consistency theorem in soft model theory, «Transactions of the AMS», 263, 231-241. Zbl0519.03031MR590421DOI10.2307/1998653
9. Mundici, D. (1982) - Compactness = JEP in any logic, «Fund. Math.», to appear. Zbl0564.03034
10. Mundici, D. (1981) - A group-theoretical invariant for elementary equivalence and its role in representations of elementary classes, «Studia Logica», to appear. Zbl0482.03013MR665720DOI10.1007/BF02584060
11. Mundici, D. - Complexity of Craig's interpolation, to appear. Zbl0507.03025
12. Mundici, D. - A lower bound for the complexity of Craig's interpolants in sentential logic, «Archv für math. Logik», to appear. Zbl0511.03004MR710362DOI10.1007/BF02023010
13. Mundici, D. (1980) - Natural limitations of algorithmic procedures in logic, «Rendiconti Accademia Nazionale Lincei», 69, 101-105. Zbl0518.03005MR670813
14. Paterson, M.S. (1976) - An introduction to Boolean function complexity, «Soc. Math, de France», Astérisque 38-39, 183-201. 
15. Savage, J.E. (1976) - The complexity of computing, Wiley, New York. Zbl0391.68025
16. Schnorr, C.P. (1976) - The network complexity and the Turing machine complexity of finite functions, «Acta Informatica», 7, 95-107. Zbl0338.02019MR421889
17. Smullyan, R.M. (1971) - First-order Logic, Springer-Verlag, Berlin. Zbl0172.28901
18. Spira, P.M. (1971) - On time-hardware complexity tradeoffs for Boolean functions, Proc. 4th Hawaii Int. Symp. on System Sciences, 525-527. 
19. Friedman, H. (1976) - The complexity of explicit definitionsy, «Advances in Math.», 20, 18-29. Zbl0355.02010