  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 equivalence, a weakened version of equivalence. In
turn, common equivalence can be expressed in terms of forgetting. An algorithm
for forgetting and checking common equivalence in polynomial space is given for
the Horn case; it is polynomial-time for the subclass of single-head formulae.
Minimizing after forgetting is polynomial-time if the formula is also acyclic
and variables cannot be introduced, NP-hard when they can.
