String rewriting and proof complexity: an interpretation of resolution

0380563 - MÚ 2013 RIV PL eng J - Journal Article
Cavagnetto, Stefano
String rewriting and proof complexity: an interpretation of resolution.
Reports on mathematical logic. Roč. 44, Jun (2009), s. 167-200. ISSN 0137-2904. E-ISSN 0137-2904
R&D Projects: GA AV ČR IAA1019401
Institutional research plan: CEZ:AV0Z10190503
Keywords : propositional logic * propositional proof complexity
Subject RIV: BA - General Mathematics
http://www.iphils.uj.edu.pl/rml/rml-44/a-cav-44.htm

We interpret the well-known propositional proof system Resolution using string rewriting systems Sigma(n)* and Sigma(n) corresponding to tree-like proofs(a) and sequence-like proofs, respectively. We give a representation of Sigma(n)* using planar diagrams.
Permanent Link: http://hdl.handle.net/11104/0211239