Satisfiability of mixed Horn formulas

DOI10.1016/j.dam.2007.02.010zbMath1122.68115OpenAlexW1968262650MaRDI QIDQ997066

Ewald Speckenmeyer, Stefan Porschen

Publication date: 19 July 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.02.010

zbMATH Keywords

fixed-parameter tractabilityquadratic formula(hidden) Horn formula(weighted) satisfiability\(q\)-Horn formulaminimal vertex cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (6)

A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors ⋮ A CNF Class Generalizing Exact Linear Formulas ⋮ A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs ⋮ Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation ⋮ On Some Aspects of Mixed Horn Formulas ⋮ On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls

Uses Software

• Ltur

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nested satisfiability
• The number of maximal independent sets in a connected graph
• On generating all maximal independent sets
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Recognition of \(q\)-Horn formulae in linear time
• Polynomial-time inference of all valid implications for Horn and related formulae
• Maximal independent sets in graphs with at most one cycle
• Maximal and maximum independent sets in graphs with at mostr cycles
• Renaming a Set of Clauses as a Horn Set
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• STACS 2004
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• On cliques in graphs

This page was built for publication: Satisfiability of mixed Horn formulas