|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 5 of 16 found articles
| Title: |
An upper bound on computing all X-minimal models |
| Author: |
Avin, Chen Ben-Eliyahu-Zohary, Rachel |
| Appeared in: |
AI communications |
| Paging: | Volume 20 (2007) nr. 2 pages 87-92 |
| Year: |
2007-07-13 |
| Contents: |
The problem of computing X-minimal models, that is, models minimal with respect to a subset X of all the atoms in a theory, is relevant for many tasks in Artificial Intelligence. Unfortunately, the problem is NP-hard. In this paper we present a non-trivial upper bound for the task of computing all X-minimal models: we show that all the X-minimal models of a propositional theory 𝒯 can be found in time time-ord-mod(𝒯)+O(#DMinModX(𝒯)n${\pmatrix{{n}\\{\lfloor \frac{n}{2}\rfloor}}}$, where time-ord-mod(𝒯) is the time it takes to find all the models of 𝒯 in a particular order, #DMinModX(𝒯) is the number of different X-minimal models of T, and |X|=n. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 5 of 16 found articles
| << previous | next >> |