15 found
Order:
  1.  26
    Interpolants, Cut Elimination and Flow Graphs for the Propositional Calculus.Alessandra Carbone - 1997 - Annals of Pure and Applied Logic 83 (3):249-299.
    We analyse the structure of propositional proofs in the sequent calculus focusing on the well-known procedures of Interpolation and Cut Elimination. We are motivated in part by the desire to understand why a tautology might be ‘hard to prove’. Given a proof we associate to it a logical graph tracing the flow of formulas in it . We show some general facts about logical graphs such as acyclicity of cut-free proofs and acyclicity of contraction-free proofs , and we give a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   14 citations  
  2.  15
    A Graphic Apology for Symmetry and Implicitness.Alessandra Carbone & Stephen Semmes - 2000 - Oxford University Press.
    Succinct representation and fast access to large amounts of data are challenges of our time. This unique book suggests general approaches of 'complexity of descriptions'. It deals with a variety of concrete topics and bridges between them, while opening new perspectives and providing promising avenues for the 'complexity puzzle'.
    Direct download  
     
    Export citation  
     
    Bookmark   6 citations  
  3.  70
    Quantified Propositional Logic and the Number of Lines of Tree-Like Proofs.Alessandra Carbone - 2000 - Studia Logica 64 (3):315-321.
    There is an exponential speed-up in the number of lines of the quantified propositional sequent calculus over Substitution Frege Systems, if one considers proofs as trees. Whether this is true also for the number of symbols, is still an open problem.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  4.  40
    Group Cancellation and Resolution.Alessandra Carbone - 2006 - Studia Logica 82 (1):73-93.
    We establish a connection between the geometric methods developed in the combinatorial theory of small cancellation and the propositional resolution calculus. We define a precise correspondence between resolution proofs in logic and diagrams in small cancellation theory, and as a consequence, we derive that a resolution proof is a 2-dimensional process. The isoperimetric function defined on diagrams corresponds to the length of resolution proofs.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  5.  20
    Logical Structures and Genus of Proofs.Alessandra Carbone - 2010 - Annals of Pure and Applied Logic 161 (2):139-149.
    Any arbitrarily complicated non-oriented graph, that is a graph of arbitrarily large genus, can be encoded in a cut-free proof. This unpublished result of Statman was shown in the early seventies. We provide a proof of it, and of a number of other related facts.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  23
    Rosser Orderings in Bimodal Logics.Alessandra Carbone & Franco Montagna - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (4):343-358.
    Direct download  
     
    Export citation  
     
    Bookmark  
  7.  8
    Samuel R. Buss. The Undecidability of K-Provability. Annals of Pure and Applied Logic, Vol. 53 , Pp. 75–102.Alessandra Carbone - 1997 - Journal of Symbolic Logic 62 (4):1480-1481.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  8.  10
    14th Workshop on Logic, Language, Information and Computation (Wollic 2007).Alex Borgida & Alessandra Carbone - 2008 - Bulletin of Symbolic Logic 14 (1):160-161.
  9.  10
    Modelling Macromolecular Networks: Two Meetings in Paris, July, 2002.François Képès & Alessandra Carbone - 2002 - Bioessays 24 (12):1188-1190.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  10.  8
    Provable Fixed Points.Much Shorter Proofs.Rosser Orderings in Bimodal Logics.Much Shorter Proofs: A Bimodal Investigation. [REVIEW]Lev D. Beklemishev, Dick de Jongh, Franco Montagna & Alessandra Carbone - 1993 - Journal of Symbolic Logic 58 (2):715.
  11.  7
    Review: Samuel R. Buss, The Undecidability of $K$-Provability. [REVIEW]Alessandra Carbone - 1997 - Journal of Symbolic Logic 62 (4):1480-1481.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  12.  22
    Much Shorter Proofs: A Bimodal Investigation.Alessandra Carbone & Franco Montagna - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (1):47-66.
  13.  4
    Rosser Orderings in Bimodal Logics.Alessandra Carbone & Franco Montagna - 1989 - Mathematical Logic Quarterly 35 (4):343-358.
    Direct download  
     
    Export citation  
     
    Bookmark  
  14.  17
    Much Shorter Proofs: A Bimodal Investigation.Alessandra Carbone & Franco Montagna - 1990 - Mathematical Logic Quarterly 36 (1):47-66.
  15.  16
    Provable Fixed Points in ${\rm I}\delta0+\omega1$.Alessandra Carbone - 1991 - Notre Dame Journal of Formal Logic 32 (4):562-572.