Craig's interpolation theorem, in computation theory
- Volume: 70, Issue: 1, page 6-11
- ISSN: 1120-6330
Access Full Article
top
Abstract
topHow to cite
topMundici, Daniele. "Craig's interpolation theorem, in computation theory." Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni 70.1 (1981): 6-11. <http://eudml.org/doc/286992>.
@article{Mundici1981,
author = {Mundici, Daniele},
journal = {Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni},
keywords = {simulation of Turing machine by Boolean sentences; length of an interpolation formula},
language = {eng},
month = {1},
number = {1},
pages = {6-11},
publisher = {Accademia Nazionale dei Lincei},
title = {Craig's interpolation theorem, in computation theory},
url = {http://eudml.org/doc/286992},
volume = {70},
year = {1981},
}
TY - JOUR
AU - Mundici, Daniele
TI - Craig's interpolation theorem, in computation theory
JO - Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti Lincei. Matematica e Applicazioni
DA - 1981/1//
PB - Accademia Nazionale dei Lincei
VL - 70
IS - 1
SP - 6
EP - 11
LA - eng
KW - simulation of Turing machine by Boolean sentences; length of an interpolation formula
UR - http://eudml.org/doc/286992
ER -
References
top- Aho, A.V., Hopcroft, J.E. and Ullman, J.D. (1974) - The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass.. Zbl0326.68005
- Bell, J.L., Machover, M. (1977) - A course in mathematical logic, North-Holland, Amsterdam. Zbl0359.02001
- Cook, S.A. (1971) - The complexity of theorem proving procedures, «Proc. Third ACM Symposium», 151-158.
- Cook, S.A. and Rechkow, R.A. (1979) - The relative efficiency of propositional proof systems, «J. Symb. Logic», 44.1, 36-50. Zbl0408.03044
- Craig, W. (1957) - Linear reasoning. A new form of the Herbrand-Gentzen theorem, «J. Symb. Logic», 22, 250-268. Zbl0081.24402
- Feferman, S. (1974) - Two notes on abstract model theory, I, «Fund. Math.», 82, 153-165, and II, ibid. 89 (1975) 111-130. Zbl0296.02026
- Monk, J.D. (1976) - Mathematical Logic, Springer-Verlag, Berlin. Zbl0354.02002MR465767
- Mundici, D. (1981) - Robinson's consistency theorem in soft model theory, «Transactions of the AMS», 263, 231-241. Zbl0519.03031MR590421DOI10.2307/1998653
- Mundici, D. (1982) - Compactness = JEP in any logic, «Fund. Math.», to appear. Zbl0564.03034
- 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
- Mundici, D. - Complexity of Craig's interpolation, to appear. Zbl0507.03025
- 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
- Mundici, D. (1980) - Natural limitations of algorithmic procedures in logic, «Rendiconti Accademia Nazionale Lincei», 69, 101-105. Zbl0518.03005MR670813
- Paterson, M.S. (1976) - An introduction to Boolean function complexity, «Soc. Math, de France», Astérisque 38-39, 183-201.
- Savage, J.E. (1976) - The complexity of computing, Wiley, New York. Zbl0391.68025
- Schnorr, C.P. (1976) - The network complexity and the Turing machine complexity of finite functions, «Acta Informatica», 7, 95-107. Zbl0338.02019MR421889
- Smullyan, R.M. (1971) - First-order Logic, Springer-Verlag, Berlin. Zbl0172.28901
- Spira, P.M. (1971) - On time-hardware complexity tradeoffs for Boolean functions, Proc. 4th Hawaii Int. Symp. on System Sciences, 525-527.
- Friedman, H. (1976) - The complexity of explicit definitionsy, «Advances in Math.», 20, 18-29. Zbl0355.02010
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.