1.  7
    Essential Structure of Proofs as a Measure of Complexity.Jaime Ramos, João Rasga & Cristina Sernadas - 2020 - Logica Universalis 14 (2):209-242.
    The essential structure of proofs is proposed as the basis for a measure of complexity of formulas in FOL. The motivating idea was the recognition that distinct theorems can have the same derivation modulo some non essential details. Hence the difficulty in proving them is identical and so their complexity should be the same. We propose a notion of complexity of formulas capturing this property. With this purpose, we introduce the notions of schema calculus, schema derivation and description complexity of (...)
    Direct download (2 more)  
    Export citation  
  2.  64
    Modulated Fibring and the Collapsing Problem.Cristina Sernadas, João Rasga & Walter A. Carnielli - 2002 - Journal of Symbolic Logic 67 (4):1541-1569.
    Fibring is recognized as one of the main mechanisms in combining logics, with great signicance in the theory and applications of mathematical logic. However, an open challenge to bring is posed by the collapsing problem: even when no symbols are shared, certain combinations of logics simply collapse to one of them, indicating that bring imposes unwanted interconnections between the given logics. Modulated bring allows a ner control of the combination, solving the collapsing problem both at the semantic and deductive levels. (...)
    Direct download (10 more)  
    Export citation  
    Bookmark   9 citations  
  3.  16
    Importing Logics.João Rasga, Amílcar Sernadas & Cristina Sernadas - 2012 - Studia Logica 100 (3):545-581.
    The novel notion of importing logics is introduced, subsuming as special cases several kinds of asymmetric combination mechanisms, like temporalization [8, 9], modalization [7] and exogenous enrichment [13, 5, 12, 4, 1]. The graph-theoretic approach proposed in [15] is used, but formulas are identified with irreducible paths in the signature multi-graph instead of equivalence classes of such paths, facilitating proofs involving inductions on formulas. Importing is proved to be strongly conservative. Conservative results follow as corollaries for temporalization, modalization and exogenous (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   3 citations  
  4.  19
    Sufficient Conditions for Cut Elimination with Complexity Analysis.João Rasga - 2007 - Annals of Pure and Applied Logic 149 (1):81-99.
    Sufficient conditions for first-order-based sequent calculi to admit cut elimination by a Schütte–Tait style cut elimination proof are established. The worst case complexity of the cut elimination is analysed. The obtained upper bound is parameterized by a quantity related to the calculus. The conditions are general enough to be satisfied by a wide class of sequent calculi encompassing, among others, some sequent calculi presentations for the first order and the propositional versions of classical and intuitionistic logic, classical and intuitionistic modal (...)
    Direct download (4 more)  
    Export citation  
    Bookmark   4 citations  
  5.  20
    Interpolation Via Translations.João Rasga, Walter Carnielli & Cristina Sernadas - 2009 - Mathematical Logic Quarterly 55 (5):515-534.
    A new technique is presented for proving that a consequence system enjoys Craig interpolation or Maehara interpolation based on the fact that these properties hold in another consequence system. This technique is based on the existence of a back and forth translation satisfying some properties between the consequence systems. Some examples of translations satisfying those properties are described. Namely a translation between the global/local consequence systems induced by fragments of linear logic, a Kolmogorov-Gentzen-Gödel style translation, and a new translation between (...)
    Direct download (3 more)  
    Export citation  
    Bookmark   2 citations  
  6.  19
    Craig Interpolation in the Presence of Unreliable Connectives.João Rasga, Cristina Sernadas & Amlcar Sernadas - 2014 - Logica Universalis 8 (3-4):423-446.
    Arrow and turnstile interpolations are investigated in UCL [introduced by Sernadas et al. ], a logic that is a complete extension of classical propositional logic for reasoning about connectives that only behave as expected with a given probability. Arrow interpolation is shown to hold in general and turnstile interpolation is established under some provisos.
    Direct download (2 more)  
    Export citation  
    Bookmark   1 citation  
  7.  25
    Completeness and Interpolation of Almost‐Everywhere Quantification Over Finitely Additive Measures.João Rasga, Wafik Boulos Lotfallah & Cristina Sernadas - 2013 - Mathematical Logic Quarterly 59 (4-5):286-302.
  8.  13
    Truth-Values as Labels: A General Recipe for Labelled Deduction.Cristina Sernadas, Luca Viganò, João Rasga & Amílcar Sernadas - 2003 - Journal of Applied Non-Classical Logics 13 (3-4):277-315.
    We introduce a general recipe for presenting non-classical logics in a modular and uniform way as labelled deduction systems. Our recipe is based on a labelling mechanism where labels are general entities that are present, in one way or another, in all logics, namely truth-values. More specifically, the main idea underlying our approach is the use of algebras of truth-values, whose operators reflect the semantics we have in mind, as the labelling algebras of our labelled deduction systems. The “truth-values as (...)
    Direct download (5 more)  
    Export citation