Minimal sets over a monotone predicate: Enumeration and counting /
V mnoha oblastech informatiky pracujeme s referenční množinou C a monotónním predikátem P : P(C) → Bool. Ona monotónnost znamená, že pokud if P(N) = True, pak P(M) = True pro každé N ⊆ M ⊆ C. Cílem je identifikovat minimální podmnožiny C které splňují predikát P; tyto podmnožiny jsou označovány zkra...
Uloženo v:
| Hlavní autor: | |
|---|---|
| Další autoři: | |
| Typ dokumentu: | VŠ práce nebo rukopis |
| Jazyk: | Angličtina |
| Vydáno: |
2021
|
| Témata: | |
| On-line přístup: | https://is.muni.cz/th/y4v8m/ |
| Shrnutí: | V mnoha oblastech informatiky pracujeme s referenční množinou C a monotónním predikátem P : P(C) → Bool. Ona monotónnost znamená, že pokud if P(N) = True, pak P(M) = True pro každé N ⊆ M ⊆ C. Cílem je identifikovat minimální podmnožiny C které splňují predikát P; tyto podmnožiny jsou označovány zkratkou MSMP z anglického Minimal Sets over a Monotone Predicate. Například, uvažme že C je nesplnitelná množina Booleovských klauzulí a P(N) = True právě když N ⊆ C je nesplnitelná. V tomto případě jsou ony MSMP nazývány minimální nesplnitelné podmnožiny C, krátce MUSes z anglického Minimal Unsatisfiable Subsets. V této disertační práci řešíme několik výpočetních problémů, které lze formulovat pomocí terminologie MSMP. V první části práce navrhujeme dva doménově univerzální algoritmy pro enumeraci MSMP, tj. algoritmy které mohou být použity pro libovolnou konkrétní instanci MSMP. Přirozenou rolí doménově univerzálních algoritmů je složit jako „ready-to-use“ řešení pro každou novou instanci MS In many areas of computer science, we are given a reference set C and a monotone predicate P : P(C) → Bool. The monotonicity means that if P(N) = True then P(M) = True for every N ⊆ M ⊆ C. The goal is to identify the Minimal Subsets of C satisfying the Monotone Predicate (MSMPs). For instance, assume that C is an unsatisfiable set of Boolean clauses and P(N) = True iff N ⊆ C is unsatisfiable. In this case, the MSMPs are the minimal unsatisfiable subsets (MUSes) of C which are often used during an analysis of unsatisfiable Boolean formulas. The contribution of the thesis is the following. In the first part, we propose two domain agnostic algorithms for MSMP enumeration, i.e. algorithms that can be applied for any particular instance of MSMPs. A natural role of domain agnostic algorithms is to serve as ready-to-use solutions for any new instance of MSMPs that might arise. In the second part, we focus on the particular instance of MSMPs where the input set C is a set of Boolean clauses |
|---|---|
| Popis jednotky: | Vedoucí práce: Ivana Černá |
| Fyzický popis: | 201 stran : ilustrace |