a counterexample to W. Bibel's and E. Eder's strong completeness result for connection graph resolution

DOI10.1145/363647.363697zbMATH Open1320.68164OpenAlexW2074221718WikidataQ124792619 ScholiaQ124792619MaRDI QIDQ2947006FDOQ2947006

Authors: Graham Wrightson, Jörg H. Siekmann 

Publication date: 20 September 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/363647.363697

Recommendations

• Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution
• scientific article; zbMATH DE number 1926639
• An open research problem: strong completeness of R Kowalski's connection graph proof procedure
• Correction to: ``Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• scientific article; zbMATH DE number 622433
• scientific article; zbMATH DE number 1189103
• Corrigendum to ``Completeness results for graph isomorphism
• scientific article; zbMATH DE number 1990687
• Near-optimal lower bounds on regular resolution refutations of Tseitin formulas for all constant-degree graphs
• Erratum to ``The monadic second-order logic of graphs. VI: On several representations of graphs by relational structures

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (1)

• An open research problem: strong completeness of R Kowalski's connection graph proof procedure

This page was built for publication: a counterexample to W. Bibel's and E. Eder's strong completeness result for connection graph resolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947006)