|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 5 van 16 gevonden artikelen
| Titel: |
An upper bound on computing all X-minimal models |
| Auteur: |
Avin, Chen Ben-Eliyahu-Zohary, Rachel |
| Verschenen in: |
AI communications |
| Paginering: | Jaargang 20 (2007) nr. 2 pagina's 87-92 |
| Jaar: |
2007-07-13 |
| Inhoud: |
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. |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 5 van 16 gevonden artikelen
| << vorige | volgende >> |