BOUNDED-ANALYTIC SEQUENT CALCULI AND EMBEDDINGS FOR HYPERSEQUENT LOGICS
Authors:
- Agata CiabattoniACAgata Ciabattoni
- Timo LangTLTimo Lang
- Revantha RamanayakeRRRevantha Ramanayake
Open Access
- 11 June 2021
- journal article
- research article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 86 (2) , 635-668
Abstract
A sequent calculus with the subformula property has long been recognised as a highly favourable starting point for the proof theoretic investigation of a logic. However, most logics of interest cannot be presented using a sequent calculus with the subformula property. In response, many formalisms more intricate than the sequent calculus have been formulated. In this work we identify an alternative: retain the sequent calculus but generalise the subformula property to permit specific axiom substitutions and their subformulas. Our investigation leads to a classification of generalised subformula properties and is applied to infinitely many substructural, intermediate, and modal logics (specifically: those with a cut-free hypersequent calculus). We also develop a complementary perspective on the generalised subformula properties in terms of logical embeddings. This yields new complexity upper bounds for contractive-mingle substructural logics and situates isolated results on the so-called simple substitution property within a general theory.Keywords
This publication has 32 references indexed in Scilit:
- THE UBIQUITY OF CONSERVATIVE TRANSLATIONSThe Review of Symbolic Logic, 2012
- Disjunction property and complexity of substructural logicsTheoretical Computer Science, 2011
- On triangular norms and uninorms definable inInternational Journal of Approximate Reasoning, 2007
- Conservative translationsAnnals of Pure and Applied Logic, 2001
- Generalized tableau systems for intermediate propositional logics1997
- The Taming of the Cut. Classical Refutations with Analytic CutJournal of Logic and Computation, 1994
- The simple substitution property of the intermediate propositional logics on finite slicesStudia Logica, 1993
- A constructive analysis of RMThe Journal of Symbolic Logic, 1987
- Pseudo two-valued evaluation method for intermediate logicsStudia Logica, 1986
- Analytic cutThe Journal of Symbolic Logic, 1969