TY - GEN
T1 - More theory revision with queries (extended abstract)
AU - Goldsmith, Judy
AU - Sloan, Robert H.
PY - 2000
Y1 - 2000
N2 - Given a Boolean formula that is not quite right, how does one fix it? That is, if a given formula differs from an unknown target formula, what is the complexity of revising the given formula? The tools available for determining the revisions are queries to membership and equivalence oracles, namely, questions of the form: "Is this an instance of the target formula," and "Is this hypothesis equivalent to the target formula?" In the latter case, if the answer is "No," the oracle returns an instance that is true for exactly one of the hypothesis and the target. For Horn sentences that require only deletion revisions, a revision algorithm is given that is polynomial in the number of clauses of the formula and the minimum number of deletions needed. For 2-term monotone DNF formulas, a revision algorithm is given that is polynomial in the minimum number of necessary deletions and additions and the logarithm of the number of variables. Previous work addressed deletion-only revisions to 2-term unate DNF formulas.
AB - Given a Boolean formula that is not quite right, how does one fix it? That is, if a given formula differs from an unknown target formula, what is the complexity of revising the given formula? The tools available for determining the revisions are queries to membership and equivalence oracles, namely, questions of the form: "Is this an instance of the target formula," and "Is this hypothesis equivalent to the target formula?" In the latter case, if the answer is "No," the oracle returns an instance that is true for exactly one of the hypothesis and the target. For Horn sentences that require only deletion revisions, a revision algorithm is given that is polynomial in the number of clauses of the formula and the minimum number of deletions needed. For 2-term monotone DNF formulas, a revision algorithm is given that is polynomial in the minimum number of necessary deletions and additions and the logarithm of the number of variables. Previous work addressed deletion-only revisions to 2-term unate DNF formulas.
UR - http://www.scopus.com/inward/record.url?scp=0033692215&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0033692215&partnerID=8YFLogxK
U2 - 10.1145/335305.335356
DO - 10.1145/335305.335356
M3 - Conference contribution
AN - SCOPUS:0033692215
SN - 1581131844
SN - 9781581131840
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 441
EP - 448
BT - Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
T2 - 32nd Annual ACM Symposium on Theory of Computing, STOC 2000
Y2 - 21 May 2000 through 23 May 2000
ER -