A lower bound for the complexity of Craig's interpolants in sentential logic

Archive for Mathematical Logic 23 (1):27-36 (1983)
  Copy   BIBTEX

Abstract

This article has no associated abstract. (fix it)

Categories

Add categories

Keywords

Reprint years

DOI

10.1007/bf02023010

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Tautologies with a unique craig interpolant, uniform vs. nonuniform complexity.Daniele Mundici - 1984 - Annals of Pure and Applied Logic 27 (3):265-273.
Interpolation.Misha Gavrilovich - 1997 - Logic Journal of the IGPL 5 (3):11-16.
On the degree of complexity of sentential logics.II. An example of the logic with semi-negation.Jacek Hawranek & Jan Zygmunt - 1984 - Studia Logica 43 (4):405 - 413.
Interpolation by a Game.Jan Kraíček - 1998 - Mathematical Logic Quarterly 44 (4):450-458.
Interpolants, cut elimination and flow graphs for the propositional calculus.Alessandra Carbone - 1997 - Annals of Pure and Applied Logic 83 (3):249-299.
The complexity of the disjunction and existential properties in intuitionistic logic.Sam Buss & Grigori Mints - 1999 - Annals of Pure and Applied Logic 99 (1-3):93-104.
A theorem of the degree of complexity of some sentential logics.Jacek Hawranek & Jan Zygmunt - 1980 - Bulletin of the Section of Logic 9 (2):67-69.
Interpolation in practical formal development.J. Bicarregui, T. Dimitrakos, D. Gabbay & T. Maibaum - 2001 - Logic Journal of the IGPL 9 (2):231-244.
Deciding the existence of uniform interpolants over transitive models.Giovanna D’Agostino & Giacomo Lenzi - 2011 - Archive for Mathematical Logic 50 (1-2):185-196.
A Lower Complexity Bound for Propositional Dynamic Logic with Intersection.M. Lange - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 133-147.
A Lower Complexity Bound for Propositional Dynamic Logic with Intersection.M. Lange - 1998 - In Marcus Kracht, Maarten de Rijke, Heinrich Wansing & Michael Zakharyaschev (eds.), Advances in Modal Logic. CSLI Publications. pp. 133-147.
On meta complexity of propositional formulas and propositional proofs.Pavel Naumov - 2008 - Archive for Mathematical Logic 47 (1):35-52.
On the degree of complexity of sentential logics. A couple of examples.Jacek Hawranek & Jan Zygmunt - 1981 - Studia Logica 40 (2):141 - 153.
Upper and lower Ramsey bounds in bounded arithmetic.Kerry Ojakian - 2005 - Annals of Pure and Applied Logic 135 (1-3):135-150.
2-Exp Time lower bounds for propositional dynamic logics with intersection.Martin Lange & Carsten Lutz - 2005 - Journal of Symbolic Logic 70 (4):1072-1086.

Analytics

Added to PP
2020-12-03

Downloads
5 (#1,543,447)

6 months
4 (#796,773)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The complexity of propositional proofs.Nathan Segerlind - 2007 - Bulletin of Symbolic Logic 13 (4):417-481.

Add more citations

References found in this work

No references found.

Add more references