Compactly Generating All Satisfying Truth Assignments of a Horn Formula
Copyright policy )Compactly Generating All Satisfying Truth Assignments of a Horn Formula
While it was known that all models of a Horn formula can be generated in output-polynomial time, here we present an explicit algorithm as opposed to the rather vague oracle-scheme suggested in the proof of [6, Thm.4]. It is an instance of some principle of exclusion that compactly (thus not one by one) generates all models of certain Boolean formulae given in CNF. The principle of exclusion can be adapted to generate only the models of weight k. We compare and contrast it with constraint programming, 0, 1 integer programming, and binary decision diagrams.
- Stellenbosch University South Africa
FOS: Computer and information sciences, Horn formula, Computer Science - Logic in Computer Science, Mathematics - Logic, 004, Logic in Computer Science (cs.LO), FOS: Mathematics, Output-polynomial algorithm, Logic (math.LO), Mathematics, Algorithms, Fixed-cardinality models
FOS: Computer and information sciences, Horn formula, Computer Science - Logic in Computer Science, Mathematics - Logic, 004, Logic in Computer Science (cs.LO), FOS: Mathematics, Output-polynomial algorithm, Logic (math.LO), Mathematics, Algorithms, Fixed-cardinality models
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!