Improved Algorithms for Theory Revision with Queries

摘要

We give a revision algorithm for monotone DNF formulas in the general revision model (additions and deletions of variables) that uses O(m~3e log n) queries, where m is the number of terms, e the revision distance to the target formula, and n 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 read-once formulas in the deletions-only model can be improved from O(e log~2 n) to O(e log n).