94 citations · 246 across the 28 of their papers we have counts for
4 papers · 1 filter
Reconstructing a single-head formula to facilitate logical forgetting
Paolo Liberatore
Logical forgetting may take exponential time in general, but it does not when its input is a single-head propositional definite Horn formula. Single-head means that no variable is…
One head is better than two: a polynomial restriction for propositional definite Horn forgetting
Paolo Liberatore
Logical forgetting is \np-complete even in the simple case of propositional Horn formulae, and may exponentially increase their size. A way to forget is to replace each variable to…
Common equivalence and size after forgetting
Paolo Liberatore
Forgetting variables from a propositional formula may increase its size. Introducing new variables is a way to shorten it. Both operations can be expressed in terms of common equiv…
The ghosts of forgotten things: A study on size after forgetting
Paolo Liberatore
Forgetting is removing variables from a logical formula while preserving the constraints on the other variables. In spite of being a form of reduction, it does not always decrease…