𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A note on the complexity of the satisfiability of modal Horn clauses

✍ Scribed by Luis Fariñas Del Cerro; Martti Penttonen

Book ID
108016217
Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
697 KB
Volume
4
Category
Article
ISSN
0743-1066

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

The horn basis of a set of clauses
The horn basis of a set of clauses
✍ Jean-Jacques Hébrard; Philippe Luquet 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 425 KB

We formalize the idea that a set of propositional clauses that is not Horn-renamable can still be partially so. We show that for any finite set of clauses S defined on a set of variables V, there exists a largest subset U of V, with regard to inclusion, such that S is Horn-renamable with respect to

On the Query Complexity of Clique Size a
On the Query Complexity of Clique Size and Maximum Satisfiability
✍ Richard Chang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 682 KB

This paper explores the bounded query complexity of approximating the size of the maximum clique in a graph (Clique Size) and the number of simultaneously satisfiable clauses in a 3CNF formula (MaxSat). The results in the paper show that for certain approximation factors, approximating Clique Size a