Reports on Mathematical Logic

No. 44


String Rewriting and Proof Complexity: an interpretation of Resolution

A b s t r a c t. We interpret the well-known propositional proof system Resolution using string rewriting systems $\Sigma^{*}_{n}$ and $\Sigma_{n}$ corresponding to tree-like proofs and sequence-like proofs, respectively. We give a representation of $\Sigma^{*}_{n}$ using planar diagrams.

Back to Main Menu