On linear rewriting systems for Boolean logic and some applications to proof theory

DOI10.2168/LMCS-12(4:9)2016zbMath1445.03069arXiv1610.08772MaRDI QIDQ2974793

Lutz Straßburger, Anupam Das

Publication date: 11 April 2017

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.08772

zbMATH Keywords

proof theoryBoolean logiclinear rewriting

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Proof-theoretic aspects of linear logic and other substructural logics (03F52) Complexity of proofs (03F20)

Related Items

Cirquent Calculus in a Nutshell ⋮ An Analytic Propositional Proof System on Graphs ⋮ Enumerating Independent Linear Inferences

Uses Software

• JBool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Linear logic
• Extension without cut
• Natural deduction and coherence for weakly distributive categories
• A game semantics for linear logic
• On read-once threshold formulae and their randomized decision tree complexity
• Complexity of Deep Inference via Atomic Flows
• Rewriting with Linear Inferences in Propositional Logic
• A Local System for Classical Logic
• On the Proof Complexity of Cut-Free Bounded Deep Inference
• Normalisation Control in Deep Inference via Atomic Flows
• Amplification by Read-Once Formulas
• Lower bounds for cutting planes proofs with small coefficients
• On the pigeonhole and related principles in deep inference and monotone systems
• A system of interaction and structure
• No complete linear term rewriting system for propositional logic
• A Characterization of Medial as Rewriting Rule
• Calcul du rapport maximal de deux normes sur $\mathbf {R}^n$