Abstrakt. Betydelsen och effekten av problemet med Boolesk tillfredsställelse (SAT) i många praktiska miljöer är välkänt. Förutom SAT, ett antal beräkningsproblem relaterade till Booleska formler hitta ett brett utbud av praktiska tillämpningar. Konkreta exempel för CNF-formler inkluderar beräkning av primära implicita (PI), minimala modeller (MM), minimala otillfredsställbara undergrupper (MUS), minimala ekvivalenta undergrupper (MES) och minimala korrigeringsundergrupper (MCSes), bland flera andra. Denna uppsats bygger på tidigare arbete av Bradley och Manna och visar att alla dessa beräkningsproblem kan ses som datorisering en minimal uppsättning föremål för en monoton predikat, dvs.. problemet med MSMP. Om dessa beräkningsproblem används som exempel på MSMP-problemet kan de därför lösas med samma algoritmer. Viktigare är att de insikter som detta resultat ger gör det möjligt att utveckla en ny algoritm för det allmänna MSMP-problemet, som är asymptotiskt optimalt. I motsats till andra asymptotiskt optimala algoritmer fungerar den nya algoritmen dessutom i praktiken på ett konkurrenskraftigt sätt. Tidningen genomför en omfattande experimentell utvärdering av den nya algoritmen om MUS-problemet och visar att den överträffar toppmoderna MUS-extraheringsalgoritmer.
I REF föreslogs också progressionsalgoritmen för MSMP-problemet.
Minimal Sets over Monotone Predicates in Boolean Formulae
{'venue': 'CAV', 'journal': None, 'mag_field_of_study': ['Computer Science']}