I need a reference that points out the fact
that quantified monotone boolean formulas
are decidable in linear time.

A monotone boolean formula is composed of ANDs
ORs and boolean variables, no negations.

They are decided, just by plugging in 0 for xj when
xj is quantified with forall, and 1 when
xj is quantified with exists.  Iff the
assignment evaluates to true, the quantification
is valid.

I remeber discussing this briefly on comp.theory
in early 1998, but I do not know any citation.
Thanks for your help, please send email.
Dan Pehoushek

Sent via Deja.com
http://www.deja.com/