A hierarchy of propositional Horn formuls

DOI10.1016/0304-3975(89)90123-0zbMATH Open0676.03026OpenAlexW2030000722MaRDI QIDQ1122571FDOQ1122571

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

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

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)

Cites Work

• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• Some simplified NP-complete graph problems
• Nondeterministic Space is Closed under Complementation
• Alternation
• On the Complexity of Timetable and Multicommodity Flow Problems
• Complete problems for deterministic polynomial time
• Title not available (Why is that?)
• Satisfiability problems for propositional calculi
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the unique satisfiability problem

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)