ONLINE ALGORITHMS FOR SATISFIABILITY PROBLEMS WITH UNCERTAINTY

In this paper the problem of the on-line satisfiability of a Horn form ula with uncertainty is addressed; we show how to represent a signific ant class of formulae by weighted directed hypergraphs and we present two algorithms that solve the on-line Horn-SAT problem and find a mini mum model for the formula working on the dynamic weighted hypergraph r epresentation. These algorithms make increasing assumptions on the for mula and we find that the second one solves the on-line Horn-SAT probl em with a total time linear in the size of the formula, matching the o ptimal result for Boolean Horn formulae.