Vi utvecklade en formell ram för konfliktdriven klausulinlärning (CDCL) med hjälp av Isabelle/HOL proof assistent. Genom en kedja av finesser kopplas en abstrakt CDCL-kalkyl först till en mer konkret analys, sedan till en SAT-lösare uttryckt i ett funktionellt programmeringsspråk, och slutligen till en SAT-lösare i ett tvingande språk, med total korrekthet garantier. Ramverket erbjuder ett bekvämt sätt att bevisa metateoremer och experimentera med varianter, inklusive Davis-Putnam-Logemann-Loveland (DPLL) kalkyl. Det imperativa programmet bygger på den två-tittade-litterära datastrukturen och andra optimeringar som finns i moderna lösare. Vi använde Isabelle's Raffination Framework för att automatisera de mest tråkiga förfining steg. De mest anmärkningsvärda aspekterna av vårt arbete är införandet av regler för glömska, omstart och stegvis lösning och tillämpning av stegvis förfining.
Blanchette och andra REF presenterar ett certifierat SAT-lösningsramverk verifierat i Isabelle/HOL proof assistent.
A Verified SAT Solver Framework with Learn, Forget, Restart, and Incrementality
{'venue': 'Journal of Automated Reasoning', 'journal': 'Journal of Automated Reasoning', 'mag_field_of_study': ['Computer Science']}