Kaavojen tyydyttävyyden ongelma teorioissa

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 15. tammikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Kaavojen tyydyttävyysongelma teorioissa ( englanniksi satisfiability modulo theories , SMT) on loogisten kaavojen ratkaistavuuden ongelma, kun otetaan huomioon niiden taustalla olevat teoriat. Esimerkkejä tällaisista SMT-kaavojen teorioista ovat: kokonaislukujen ja reaalilukujen teoriat, listateoriat, taulukot, bittivektorit jne.

Peruskäsitteet

Muodollisesti SMT-kaava on ensimmäisen asteen logiikassa kaava , jossa joillakin funktioilla ja predikaattisymboleilla on lisätulkinta. Tehtävänä on selvittää, onko annettu kaava toteutettavissa. Toisin sanoen, toisin kuin Boolen kaavojen tyydyttävyysongelma , SMT-kaava sisältää Boolen muuttujien sijasta mielivaltaisia muuttujia, ja predikaatit ovat näiden muuttujien Boolen funktioita.

Esimerkkejä predikaateista ovat lineaariset epäyhtälöt ( ) tai yhtäläisyydet, jotka sisältävät niin sanottuja tulkitsemattomia termejä tai funktiosymboleja : , jossa on jokin kahden argumentin määrittelemätön funktio. Predikaatit tulkitaan sen teorian mukaan, johon ne kuuluvat. Esimerkiksi reaalimuuttujien lineaariset epäyhtälöt arvioidaan lineaarisen reaaliaritmeettisen teorian sääntöjen mukaan, kun taas tulkitsemattomien termien ja funktiosymbolien predikaatit arvioidaan yhtäläisten tulkitsemattomien funktioiden teorian sääntöjen mukaan (kutsutaan myös tyhjäksi teoriaksi). . SMT sisältää myös taulukko- ja listateoriat (käytetään usein ohjelmien mallintamiseen ja todentamiseen ) ja bittivektoriteoriat (käytetään usein laitteiston mallintamiseen ja todentamiseen). Myös osateoriat ovat mahdollisia: esimerkiksi erologiikka on lineaarisen aritmeettisen aliteoria, jossa epäyhtälöt rajoittuvat seuraavaan muotoon muuttujille ja ja vakiolle . $3x+2y-z\geqslant 4$ $f(f(u,v),v)=f(u,v)$ $f$ $xy\leq c$ $x$ $y$ $c$

Useimmat SMT - ratkaisijat tukevat vain ei- kvantifiointikaavoja .

SMT:n ilmaisuvoima

SMT-kaava on Boolen SAT-kaavan yleistys, jossa muuttujat korvataan asiaankuuluvien teorioiden predikaateilla. Siksi SMT:t tarjoavat enemmän mallinnusvaihtoehtoja kuin SAT-kaavat. Esimerkiksi SMT-kaavan avulla voit mallintaa mikroprosessorimoduulien funktioita sanatasolla bittitason sijaan .

SMT-ratkaisijat

Ensimmäiset yritykset ratkaista SMT-ongelmia pyrittiin muuntamaan ne SAT-kaavoiksi (esimerkiksi 32-bittiset muuttujat koodattiin 32 Boolen muuttujalla, jotka koodasivat vastaavat operaatiot sanoilla matalan tason operaatioiksi biteille) ja SAT-kaavan ratkaisemiseen ratkaisija. Tällä lähestymistavalla on etunsa - sen avulla voit käyttää olemassa olevia SAT-ratkaisijoita ilman muutoksia ja käyttää niissä tehtyjä optimointeja. Toisaalta taustalla olevien teorioiden korkean tason semantiikan menettäminen tarkoittaa, että SAT-ratkaisijan täytyy tehdä paljon vaivaa päätelläkseen "ilmeisiä" tosiasioita (kuten lisäämistä varten). Tämä harkinta on johtanut erikoistuneisiin SMT-ratkaisimiin, jotka integroivat tavanomaiset DPLL -tyyliset loogiset todisteet teoriakohtaisiin ratkaisijoihin ( T-solvers ), jotka toimivat tietyn teorian predikaattien disjunktioiden ja konjunktioiden kanssa. $x+y=y+x$

DPLL(T)-arkkitehtuuri siirtää Boolen todistusfunktiot SAT-ratkaisijalle, joka vuorostaan on vuorovaikutuksessa teorian T ratkaisijan kanssa. SAT-ratkaisija luo malleja, joissa osa ilman negaatiota saapuvista literaaleista ei ole Boolen muuttujia, vaan atomilauseita. joidenkin, mahdollisesti monilajiteltujen, ensimmäisen asteen teorian. Teoriaratkaisija yrittää löytää epäjohdonmukaisuuksia sille välitetyistä malleista, ja jos tällaista epäjohdonmukaisuutta ei löydy, kaava julistetaan tyydyttäväksi. Jotta tämä integraatio toimisi, teoriaratkaisijan on osallistuttava konfliktin analysointiin antamalla selitykset mahdottomuudesta konfliktien sattuessa , jotka tallennetaan DPLL-arkkitehtuuriin perustuvaan ratkaisijaan. Koska SAT-mallien määrä on äärellinen, numerointi johtaa vastaukseen äärellisessä ajassa [1] .

Tuetut ja aktiivisesti kehitetyt ratkaisijat: Alt-Ergo, Barcelogic, Beaver, Boolector, CVC3, DPT, MathSAT, OpenSMT, SatEEn, Spear, STP, UCLID, veriT, Yices, Z3.
Muut: Argo-lib, Ario, CVC, CVC Lite, Fx7, haRVey, HTP, ICS, LPSAT, RDL, Sammy, Simplify, Simplics, STeP, SVC, Tsat++.

Muistiinpanot

↑ M. Armand, G. Faure, B. Gregoire, C. Keller, L. Thery, B. Werner. SAT/SMT Solversin modulaarinen integrointi Coqiin Proof Witnesses First International Conferencen kautta, CPP 2011, Kenting, Taiwan, 7.-9.12.2011. Proceedings. DOI 10.1007/978-3-642-25379-9_12

Kirjallisuus

Nieuwenhuis, R.; Oliveras, A.; Tinelli, C. SAT- ja SAT-moduuliteorioiden ratkaiseminen: Abstraktista Davis-Putnam-Logemann-Loveland-menettelystä DPLL:hen( T ) // Journal of the ACM. - 2006. - T. 53 , nro 6 . - s. 937-977.
Biere, A. ja Gomes, CP Theory and Applications of Satisfiability Testing - SAT 2006: 9th International Conference, Seattle, WA, USA, 12.-15.8.2006, Proceedings . — Springer, 2006. — s . 142-155 . — 438 s. — ISBN 9783540372066 .
D.Yurichev, Nopea johdatus SAT/SMT-ratkaisijoihin ja symboliseen toteutukseen