##
Reports on Mathematical Logic

###
No. 44

Stefano CAVAGNETTO

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