Improved Algorithms for Theory Revision with Queries
Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán · 2000
We give a revision algorithm for monotone DNF formulas in the general revision model (additions and deletions of variables) that uses £¥¤§¦©¨������������ queries, where ¦ is the number of terms, � the revision distance to the target formula, and � the number of variables. We also give an algorithm for revising 2-term unate DNF formulas in the same model, with a similar query bound. Lastly, we show that the earlier query bound on revising readonce formulas in the deletions-only model can be improved from £¥¤§������������ � to £¥¤����������� �. 1