Satisfiability of mixed Horn formulas

DOI10.1016/J.DAM.2007.02.010zbMATH Open1122.68115OpenAlexW1968262650MaRDI QIDQ997066FDOQ997066

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

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Renaming a Set of Clauses as a Horn Set
• On cliques in graphs
• Nested satisfiability
• On generating all maximal independent sets
• The Number of Maximal Independent Sets in Triangle-Free Graphs
• The number of maximal independent sets in a connected graph
• STACS 2004
• Maximal independent sets in graphs with at most one cycle
• Maximal and maximum independent sets in graphs with at mostr cycles
• A satisfiability formulation of problems on level graphs
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing

Cited In (14)

• A CNF Class Generalizing Exact Linear Formulas
• Satisfiability Checking of Non-clausal Formulas Using General Matings
• Horn logic, search and satisfiability. A collection of papers in memory of Robert G. Jeroslow
• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation
• On a generalization of Horn constraint systems
• The satisfiabilty problem for a class consisting of horn sentences and some non-horn sentences in proportional logic
• Satisfiability on mixed instances
• A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs
• On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls
• SAT-Based Horn Least Upper Bounds
• On Some Aspects of Mixed Horn Formulas
• Title not available (Why is that?)
• A New Bound for an NP-Hard Subclass of 3-SAT Using Backdoors
• Unique Horn renaming and Unique 2-Satisfiability

Uses Software

• Ltur

Recommendations

• Title not available (Why is that?) 👍 👎
• On the complexity of the maximum satisfiability problem for Horn formulas 👍 👎
• Satisfiability of co-nested formulas 👍 👎
• On a generalization of Horn constraint systems 👍 👎
• A note on the complexity of the satisfiability of modal Horn clauses 👍 👎
• Satisfiability in composition-nominative logics 👍 👎
• Satisfiability on mixed instances 👍 👎
• SAT-Based Horn Least Upper Bounds 👍 👎
• On Some Aspects of Mixed Horn Formulas 👍 👎
• Combined Satisfiability Modulo Parametric Theories 👍 👎

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

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