Classical and Intuitionistic Subexponential Logics are Equally Expressive

Kaustuv Chaudhuri 1
1 PARSIFAL - Proof search and reasoning with logic specifications
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : It is standard to regard the intuitionistic restriction of a classical logic as increasing the expressivity of the logic because the classical logic can be adequately represented in the intuitionistic logic by double-negation, while the other direction has no truth-preserving propositional encodings. We show here that subexponential logic, which is a family of substructural refinements of classical logic, each parametric over a preorder over the subexponential connectives, does not suffer from this asymmetry if the preorder is systematically modified as part of the encoding. Precisely, we show a bijection between synthetic (i.e., focused) partial sequent derivations modulo a given encoding. Particular instances of our encoding for particular subexponential preorders give rise to both known and novel adequacy theorems for substructural logics.
Type de document :
Communication dans un congrès
Anuj Dawar and Helmut Veith. Computer Science Logic, Aug 2010, Brno, Czech Republic. Springer, 6247, pp.185--199, 2010, LNCS. 〈10.1007/978-3-642-15205-4_17〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00534865
Contributeur : Kaustuv Chaudhuri <>
Soumis le : mercredi 10 novembre 2010 - 16:38:50
Dernière modification le : jeudi 10 mai 2018 - 02:06:28
Document(s) archivé(s) le : vendredi 11 février 2011 - 03:15:38

Fichiers

clasint.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Kaustuv Chaudhuri. Classical and Intuitionistic Subexponential Logics are Equally Expressive. Anuj Dawar and Helmut Veith. Computer Science Logic, Aug 2010, Brno, Czech Republic. Springer, 6247, pp.185--199, 2010, LNCS. 〈10.1007/978-3-642-15205-4_17〉. 〈inria-00534865〉

Partager

Métriques

Consultations de la notice

245

Téléchargements de fichiers

131