ML Anthology

Improved Algorithms for Theory Revision with Queries

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán
COLT 2000 pp. 236-247
/colt/2000/goldsmith2000colt-improved/

Abstract

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

Semantic Scholar

Cite

Text

Goldsmith et al. "Improved Algorithms for Theory Revision with Queries." Annual Conference on Computational Learning Theory, 2000.

Markdown

[Goldsmith et al. "Improved Algorithms for Theory Revision with Queries." Annual Conference on Computational Learning Theory, 2000.](https://mlanthology.org/colt/2000/goldsmith2000colt-improved/)

BibTeX

@inproceedings{goldsmith2000colt-improved,
  title     = {{Improved Algorithms for Theory Revision with Queries}},
  author    = {Goldsmith, Judy and Sloan, Robert H. and Szörényi, Balázs and Turán, György},
  booktitle = {Annual Conference on Computational Learning Theory},
  year      = {2000},
  pages     = {236-247},
  url       = {https://mlanthology.org/colt/2000/goldsmith2000colt-improved/}
}