On the relative proof complexity of deep inference via atomic flows
We consider the proof complexity of the minimal complete fragment, KS, of standard deep inference systems for propositional logic. To examine the size of proofs we employ atomic flows, diagrams that trace structural changes through a proof but ignore logical information. As results we obtain a polyn...
Main Author: | Anupam Das |
---|---|
Format: | Article |
Language: | English |
Published: |
Logical Methods in Computer Science e.V.
2015-03-01
|
Series: | Logical Methods in Computer Science |
Subjects: | |
Online Access: | https://lmcs.episciences.org/735/pdf |
Similar Items
-
Normalisation Control in Deep Inference via Atomic Flows
by: Alessio Guglielmi, et al.
Published: (2008-03-01) -
On the logical complexity of cyclic arithmetic
by: Anupam Das
Published: (2020-01-01) -
A Proof of Kamp's theorem
by: Alexander Rabinovich
Published: (2014-02-01) -
Bijective proofs for Eulerian numbers of types B and D
by: Luigi Santocanale
Published: (2023-03-01) -
Enumerating Independent Linear Inferences
by: Anupam Das, et al.
Published: (2023-05-01)