Loading...
Please wait, while we are loading the content...
Similar Documents
Improved Algorithms for Theory Revision with Queries ( Extended Abstract )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Goldsmith, J. |
| Copyright Year | 2000 |
| Abstract | We give a revision algorithm for monotone DNF formulas in the general revision model (additions and deletions of variables) that uses O(m3e logn) queries, wherem is the number of terms, e the revision distance to the target formula, andthe 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 fromO(e log2 n) toO(e logn). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.uky.edu/~goldsmit/papers/revisions2.ps |
| Alternate Webpage(s) | http://www.researchgate.net/profile/Judy_Goldsmith/publication/228538239_Improved_Algorithms_for_Theory_Revision_with_Queries_(Extended_Abstract)/links/0912f50d07f860c196000000.pdf |
| Alternate Webpage(s) | https://www.researchgate.net/profile/Judy_Goldsmith/publication/228538239_Improved_Algorithms_for_Theory_Revision_with_Queries_(Extended_Abstract)/links/0912f50d07f860c196000000.pdf |
| Alternate Webpage(s) | http://www.cs.uic.edu/~sloan/my-papers/colt-2000.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
