A hierarchy of propositional Horn formuls

DOI10.1016/0304-3975(89)90123-0MaRDI QIDQ1122571zbMATH OpenOpenAlexFDO

Authors Bogdan S. Chlebus

Publication date 1989

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(89)90123-0

zbMATH Keywords

bounded- depth circuitshierarchy of propositional Horn formulasnumber of alternations between players in a gamesatisfiability of Horn formulas

Mathematics Subject Classification ID

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

Recommendations

• A hierarchy of tractable satisfiability problems
• On generalized Horn formulas and k-resolution
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• scientific article; zbMATH DE number 4085614
• Hierarchies of polynomially solvable satisfiability problems

Cites work

• scientific article; zbMATH DE number 3889430 (Why is no real title available?)
• scientific article; zbMATH DE number 3568056 (Why is no real title available?)
• scientific article; zbMATH DE number 3395363 (Why is no real title available?)
• Alternation
• Complete problems for deterministic polynomial time
• Nondeterministic Space is Closed under Complementation
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the unique satisfiability problem
• Satisfiability problems for propositional calculi
• Some simplified NP-complete graph problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures

Cited in

(3)

• Refined hierarchy of formulas
• Complexity of the problem of being equivalent to Horn formulas
• Characterization results for d-Horn formulas, or on formulas that are true on dual reduced products

This page was built for publication: A hierarchy of propositional Horn formuls

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