Minimal Unembedded Renamable Horn Sets

摘要

A set of Horn clauses S is that each clause in it contains at most one positive literal. The set of Horn clauses is widely used because its satisfiability problem can be solved in linear time. A clause set S is a renamable Horn if the result replacing part prepositional variable by its complement is Horn. It has been established that the renamable Horn problem can be solved in linear time, but the maximum renamable Horn problem is NP-hard. In this paper, we concetrate on the Horn satisfiability and the maximal Horn satisfiability, based on them, we give a definition of the minimal unembedded renamable Horn set(RHS) for variable and literal and present a theorem about the minimal unembedded RHS. Then the problem of the minimal unembedded RHS has the same complexity with the minimal unsatisfiability of Horn clauses.