Tractable and intractable classes of propositional schemata

DOI10.1093/LOGCOM/EXU013MaRDI QIDQ5498869zbMATH OpenOpenAlexFDO

Authors Nicolas Peltier

Publication date 11 February 2015

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exu013

zbMATH Keywords

bounded quantifierscomplexityiterated schematapropositional logicsatisfiability problem

Mathematics Subject Classification ID

Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity of the satisfiability problem for a class of propositional schemata
• Decidability and undecidability results for propositional schemata
• A decidable class of nested iterated schemata
• A Schemata Calculus for Propositional Logic
• Reasoning on schemata of formulæ

Cited in

(5)

• Koepke machines and satisfiability for infinitary propositional languages
• Decidability and undecidability results for propositional schemata
• Complexity of the satisfiability problem for a class of propositional schemata
• scientific article; zbMATH DE number 1286031 (Why is no real title available?)
• The complexity of the satisfiability problem for Krom formulas

This page was built for publication: Tractable and intractable classes of propositional schemata

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