Results 31 to 40 of about 658,878 (281)
The Role of Quantifier Alternations in Cut Elimination
Notre Dame Journal of Formal Logic, 2003 Extending previous results from the author's master's thesis, subsequently published in the proceedings of CSL 2003, on the complexity of cut elimination for the sequent calculus LK, we discuss the role of quantifier alternations and develop a measure ...
Gerhardy, Philipp
core +5 more sources
Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic [PDF]
Logical Methods in Computer Science, 2023 This paper introduces the exponential substitution calculus (ESC), a new presentation of cut elimination for IMELL, based on proof terms and building on the idea that exponentials can be seen as explicit substitutions.
Beniamino Accattoli
doaj +1 more source
Analytic Non-Labelled Proof-Systems for Hybrid Logic: Overview and a couple of striking facts
Bulletin of the Section of Logic, 2022 This paper is about non-labelled proof-systems for hybrid logic, that is, proofsystems where arbitrary formulas can occur, not just satisfaction statements.
Torben Braüner
doaj +1 more source
Cut elimination by unthreading
Archive for Mathematical Logic, 2023 AbstractWe provide a non-Gentzen, though fully syntactical, cut-elimination algorithm for classical propositional logic. The designed procedure is implemented on $$\textsf{GS4}$$ GS 4 , the one-sided version of Kleene’s sequent system $$\textsf{G4}$$
openaire +4 more sources
Schema Complexity in Propositional-Based Logics
Mathematics, 2021 The essential structure of derivations is used as a tool for measuring the complexity of schema consequences in propositional-based logics. Our schema derivations allow the use of schema lemmas and this is reflected on the schema complexity.
Jaime Ramos +2 more
doaj +1 more source
Quasipolynomial Normalisation in Deep Inference via Atomic Flows and Threshold Formulae [PDF]
Logical Methods in Computer Science, 2016 Je\v{r}\'abek showed that cuts in classical propositional logic proofs in deep inference can be eliminated in quasipolynomial time. The proof is indirect and it relies on a result of Atserias, Galesi and Pudl\'ak about monotone sequent calculus and a ...
Paola Bruscoli +3 more
doaj +1 more source
Cut-Free Gentzen Sequent Calculi for Tense Logics
Axioms, 2023 The cut-free single-succedent Gentzen sequent calculus GKt for the minimal tense logic Kt is introduced. This sequent calculus satisfies the displaying property.
Zhe Lin, Minghui Ma
doaj +1 more source
Cut-elimination for knowledge logics with interaction
Lietuvos Matematikos Rinkinys, 2008 In the article, multimodal logics K4n and S4n with the central agent axiom are analysed. The Hilbert type calculi are presented, then the Gentzen type calculi with cut are derived, and the proofs of the cut-eliminationtheorems are outlined.
Julius Andrikonis
doaj +1 more source
Cut-Simulation and Impredicativity [PDF]
Logical Methods in Computer Science, 2009 We investigate cut-elimination and cut-simulation in impredicative (higher-order) logics. We illustrate that adding simple axioms such as Leibniz equations to a calculus for an impredicative logic -- in our case a sequent calculus for classical type ...
Christoph Benzmueller +2 more
doaj +1 more source
Confluence for classical logic through the distinction between values and computations [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 We apply an idea originated in the theory of programming languages - monadic meta-language with a distinction between values and computations - in the design of a calculus of cut-elimination for classical logic.
José Espírito Santo +3 more
doaj +1 more source