Logical structures and genus of proofs

DOI10.1016/J.APAL.2009.05.007MaRDI QIDQ1035649zbMATH OpenOpenAlexWikidataFDO

Authors Alessandra Carbone

Publication date 4 November 2009

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2009.05.007

zbMATH Keywords

cutsequent calculuscut-free proofgenus of a prooflogical flow graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Structure of proofs (03F07) Complexity of proofs (03F20)

Recommendations

• The complexity of Gentzen systems for propositional logic
• The cost of a cycle is a square
• Duplication of directed graphs and exponential blow up of proofs
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Making proofs without Modus Ponens: An introduction to the combinatorics and complexity of cut elimination

Cites work

• scientific article; zbMATH DE number 1493054 (Why is no real title available?)
• scientific article; zbMATH DE number 3333259 (Why is no real title available?)
• Duplication of directed graphs and exponential blow up of proofs
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Streams and strings in formal proofs.
• The undecidability of \(k\)-provability

Cited in

(7)

• The genus of regular languages and directed graph emulators
• Interpolants, cut elimination and flow graphs for the propositional calculus
• Two-dimensional proof-structures and the exchange rule
• Ancestral Logic: A Proof Theoretical Study
• Graphs of plural cuts
• 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
• The genus of regular languages

This page was built for publication: Logical structures and genus of proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1035649)