A short note on some tractable cases of the satisfiability problem.
type: Item
instance of: scholarly article
title: A short note on some tractable cases of the satisfiability problem.
zbMATH Open document ID: 1046.68542
author: Hans van Maaren
published in: Information and Computation
publication date: 2003-01-14T00:00:00Z
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1853103
zbMATH Keywords: CNF formulas
MaRDI profile type: Publication
full work available at URL: inco.2000.2867
OpenAlex ID: W2060398342
cites work: A linear-time algorithm for testing the truth of certain quantified Boolean formulas
cites work: A Complexity Index for Satisfiability Problems
cites work: Recognition of \(q\)-Horn formulae in linear time
cites work: Extended Horn sets in propositional logic
cites work: A class of logic problems solvable by linear programming
cites work: Linear-time algorithms for testing the satisfiability of propositional horn formulae
cites work: Q4375759
cites work: Investigations on autark assignments
cites work: Renaming a Set of Clauses as a Horn Set
cites work: Solving satisfiability in less than \(2^ n\) steps
cites work: On finding solutions for extended Horn formulas
cites work: A note on Dowling and Gallier's top-down algorithm for propositional Horn satisfiability
cites work: Alpha-balanced graphs and matrices and GF(3)-representability of matroids
cites work: Solving satisfiability problems using elliptic approximations -- effective branching rules
DOI: 10.1006/INCO.2000.2867
description: scientific article; zbMATH DE number 1853103