%0 Journal Article %1 ganter2005pseudomodels %A Ganter, Bernhard %A Krauße, Rüdiger %C Amsterdam, The Netherlands %D 2005 %I Elsevier Science Publishers B. V. %J Discrete Applied Mathematics %K %N 1 %P 43--55 %R 10.1016/j.dam.2004.06.019 %T Pseudo-models and propositional Horn inference %U http://www.math.tu-dresden.de/~ganter/psfiles/pseudo.ps %V 147 %X A well-known result is that the inference problem for propositional Horn formulae can be solved in linear time. We show that this remains true even in the presence of arbitrary (static) propositional background knowledge. Our main tool is the notion of a cumulated clause, a slight generalization of the usual clauses in Propositional Logic. We show that each propositional theory has a canonical irredundant base of cumulated clauses, and present an algorithm to compute this base.

@article{ganter2005pseudomodels, abstract = {A well-known result is that the inference problem for propositional Horn formulae can be solved in linear time. We show that this remains true even in the presence of arbitrary (static) propositional background knowledge. Our main tool is the notion of a cumulated clause, a slight generalization of the usual clauses in Propositional Logic. We show that each propositional theory has a canonical irredundant base of cumulated clauses, and present an algorithm to compute this base. }, added-at = {2011-01-29T16:45:11.000+0100}, address = {Amsterdam, The Netherlands}, author = {Ganter, Bernhard and Krauße, Rüdiger}, biburl = {https://www.bibsonomy.org/bibtex/2bd3394df55a858ed1a516a6999788c25/jaeschke}, doi = {10.1016/j.dam.2004.06.019}, interhash = {75396eab79cd8133f85c88794ac80a61}, intrahash = {bd3394df55a858ed1a516a6999788c25}, issn = {0166-218X}, journal = {Discrete Applied Mathematics}, keywords = {}, month = apr, number = 1, pages = {43--55}, publisher = {Elsevier Science Publishers B. V.}, timestamp = {2011-09-22T11:56:28.000+0200}, title = {Pseudo-models and propositional Horn inference}, url = {http://www.math.tu-dresden.de/~ganter/psfiles/pseudo.ps}, volume = 147, year = 2005 }