The expected complexity of analytic tableaux analyses in propositional calculus. II

DOI10.1007/BF01531029MaRDI QIDQ1353995zbMATH OpenOpenAlexFDO

Authors John W. Rosenthal

Publication date 13 May 1997

Published in Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01531029

zbMATH Keywords

complexitysatisfiabilitytruth tablesanalytic tableaux algorithm for SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• The proof complexity of analytic and clausal tableaux
• The complexity of analytic tableaux
• The complexity of analytic tableaux
• scientific article; zbMATH DE number 1390276
• On the complexity of propositional calculus formulae
• scientific article; zbMATH DE number 5263419
• Analytic tableaux for higher-order logic with choice
• Analytic tableaux for higher-order logic with choice
• scientific article; zbMATH DE number 5722456
• The computational complexity of propositional cirquent calculus

Cites work

• scientific article; zbMATH DE number 4102824 (Why is no real title available?)
• scientific article; zbMATH DE number 3274715 (Why is no real title available?)
• scientific article; zbMATH DE number 3308309 (Why is no real title available?)
• An Analysis of Backtracking with Search Rearrangement
• An Average Time Analysis of Backtracking
• Asymptotic Methods in Enumeration
• Average time analyses of simplified Davis-Putnam procedures
• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Corrigendum to ``Average time analyses of simplified Davis-Putnam procedures
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Stirling numbers of the second kind
• The expected complexity of analytic tableaux analyses in propositional calculus
• The probability of pure literals

Cited in

(3)

• The relative complexity of analytic tableaux and SL-resolution
• A bibliography on analytic tableaux theorem proving
• The complexity of analytic tableaux

This page was built for publication: The expected complexity of analytic tableaux analyses in propositional calculus. II

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