Minimal sets over a monotone predicate: Enumeration and counting - Bendík, Jaroslav (2021)
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