Att konstruera algoritmer som effektivt kan konstruera minimala modeller av CNFs är en viktig uppgift i AI. Denna uppsats ger nya resultat längs denna forskningslinje och presenterar nya algoritmer för att utföra minimal modellsökning och kontroll över positiva propositionella CNF:er och modellminimering över propositionella CNF:er. En algoritmisk schema, som kallas Generalized Elimination Algorithm (GEA) presenteras, som beräknar en minimal modell av någon positiv CNF. Schemat generaliserar elimineringen Algoritm (EA) [5], som beräknar en minimal modell av positiva huvudcykelfria (HCF) CNF-teorier. Medan EA alltid körs i polynom tid i storleken på den ingående HCF CNF, komplexiteten i GEA beror på komplexiteten hos den specifika eliminerande operatör som åberopas där, vilket i allmänhet kan visa sig vara exponentiellt. Därför definieras en specifik eliminerande operatör genom vilken GEA beräknar, i polynom tid, en minimal modell för en klass av CNF som strikt omfattar huvud-elementär-set-fri (HEF) CNF teorier [14], som i sin tur bildar en strikt superuppsättning av HCF teorier. Dessutom föreslås en "ofullständig" variant av GEA (kallad IGEA) för att hantera den höga komplexiteten i samband med erkännande av HEF-teorier: den resulterande schemat, som en gång omedelbart med en lämplig elimineringsoperatör, alltid konstruerar en modell av den ingående CNF, vilket garanterat är minimalt om inmatningsteorin är HEF. Mot bakgrund av ovanstående resultat är det viktigaste bidraget från detta arbete en utvidgning av farbarheten.
Effektiv polynomalgoritmer för en underklass av positiva CNF teorier föreslogs i REF.
On the Tractability of Minimal Model Computation for Some CNF Theories
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}