Teorie modulové uspokojivosti - Satisfiability modulo theories

Ve vědě o počítačích a matematické logiky , že satisfiability modulo teorie ( SMT ), problémem je rozhodovací problém pro logické vzorců s ohledem na kombinace pozadí teoriemi vyjádřenými v klasické logiky prvního řádu týkající se rovnosti. Příklady teorií obvykle používaných v informatice jsou teorie reálných čísel , teorie celých čísel a teorie různých datových struktur, jako jsou seznamy , pole , bitové vektory atd. SMT lze považovat za formu problému s uspokojením omezení a tedy za určitý formalizovaný přístup k programování omezení .

Základní terminologie

Formálně vzato, instance SMT je vzorec v logice prvního řádu , kde některé symboly funkcí a predikátů mají další interpretace, a SMT je problém určení, zda je takový vzorec uspokojivý. Jinými slovy, představte si instanci problému Booleovské uspokojivosti (SAT), ve kterém jsou některé z binárních proměnných nahrazeny predikáty nad vhodnou sadou nebinárních proměnných. Predikát je binární funkce nebinárních proměnných. Příklad predikátů zahrnuje lineární nerovnosti (např. ) Nebo rovnosti zahrnující neinterpretované termíny a funkční symboly (např. Kde je nějaká nespecifikovaná funkce dvou argumentů). Tyto predikáty jsou klasifikovány podle každé přiřazené teorie. Například lineární nerovnosti nad reálnými proměnnými se hodnotí pomocí pravidel teorie lineární reálné aritmetiky , zatímco predikáty zahrnující neinterpretované termíny a funkční symboly se hodnotí pomocí pravidel teorie neinterpretovaných funkcí s rovností (někdy označované jako prázdná teorie) ). Mezi další teorie patří teorie polí a struktur seznamů (užitečné pro modelování a ověřování počítačových programů ) a teorie bitových vektorů (užitečné při modelování a ověřování návrhů hardwaru ). Možné jsou také subteorie: například diferenční logika je sub-teorie lineární aritmetiky, ve které je každá nerovnost omezena tak, aby měla formu proměnných a a konstant . ${\ displaystyle 3x + 2y-z \ geq 4}$ ${\ displaystyle f (f (u, v), v) = f (u, v)}$ ${\ displaystyle f}$ ${\ displaystyle xy> c}$ ${\ displaystyle x}$ ${\ displaystyle}$ ${\ displaystyle c}$

Většina řešitelů SMT podporuje pouze fragmenty jejich logiky bez kvantifikátorů .

Expresivní síla

Instance SMT je zobecněním booleovské instance SAT, ve které jsou různé sady proměnných nahrazeny predikáty z různých základních teorií. SMT vzorce poskytují mnohem bohatší modelovací jazyk, než je možné u booleovských vzorců SAT. Například vzorec SMT nám umožňuje modelovat operace datových cest mikroprocesoru spíše na úrovni slova než na bitové úrovni.

Pro srovnání je programování sady odpovědí také založeno na predikátech (přesněji na atomových větách vytvořených z atomového vzorce ). Na rozdíl od SMT programy odpovědí nemají kvantifikátory a nemohou snadno vyjádřit omezení, jako je lineární aritmetika nebo rozdílová logika - ASP je v nejlepším případě vhodný pro booleovské problémy, které se redukují na volnou teorii neinterpretovaných funkcí. Implementace 32bitových celých čísel jako bitvektorů v ASP trpí většinou stejných problémů, kterým čelili první řešitelé SMT: „zjevné“ identity jako x + y = y + x je obtížné odvodit.

Logické programování omezení poskytuje podporu pro lineární aritmetická omezení, ale v úplně jiném teoretickém rámci. Řešitelé SMT byly také rozšířeny o řešení vzorců v logice vyššího řádu .

Řešitel se blíží

První pokusy o řešení instancí SMT zahrnovaly jejich překlad do booleovských instancí SAT (např. 32bitová celočíselná proměnná by byla kódována 32 jednobitovými proměnnými s odpovídajícími váhami a operace na úrovni slov, jako například „plus“, byly nahrazeny nižšími logické operace na bitech) a předání tohoto vzorce booleovskému řešení SAT. Tento přístup, který je označován jako v horlivého přístupu , má své přednosti: předběžným zpracováním SMT vzorec do ekvivalentního Logická SAT vzorce stávající Logická SAT řešitelů lze použít „tak jak je“ a jejich výkon a kapacitu zlepšení hybnou silou v průběhu času . Na druhé straně ztráta sémantiky vysokých úrovní základních teorií znamená, že booleovský SAT řešitel musí pracovat mnohem více, než je nutné, aby objevil „zjevná“ fakta (například pro sčítání celých čísel). Toto pozorování vedlo k vývoj řady řešičů SMT, které úzce integrují logické uvažování hledání stylu DPLL s řešiteli specifickými pro teorii ( řešiči T ), kteří zpracovávají spojky (AND) predikátů z dané teorie. Tento přístup se označuje jako je líný přístup . ${\ displaystyle x + y = y + x}$

Tato architektura, přezdívaná DPLL (T) , dává zodpovědnost booleovského uvažování řešení SAT SAT založenému na DPLL, které zase interaguje s řešitelem teorie T prostřednictvím dobře definovaného rozhraní. Řešitel teorie si musí dělat starosti s kontrolou proveditelnosti spojek teoretických predikátů, které mu byly předány ze SAT řešiče, protože zkoumá booleovský vyhledávací prostor vzorce. Aby tato integrace fungovala dobře, musí být řešitel teorie schopen podílet se na šíření a analýze konfliktů, tj. Musí být schopen odvodit nová fakta z již zjištěných skutečností a poskytnout stručné vysvětlení neproveditelnosti, když dojde ke konfliktu teorie vzniknout. Jinými slovy, řešitel teorie musí být přírůstkový a zpětně vysledovatelný .

SMT pro nerozhodnutelné teorie

Většina běžných přístupů SMT podporuje rozhodné teorie. Mnoho systémů v reálném světě však lze modelovat pouze pomocí nelineární aritmetiky nad reálnými čísly zahrnujícími transcendentální funkce , např. Letadlo a jeho chování. Tato skutečnost motivuje k rozšíření problému SMT na nelineární teorie, např. Zda

{\ displaystyle {\ begin {pole} {lr} & (\ sin (x) ^ {3} = \ cos (\ log (y) \ cdot x) \ vee b \ vee -x ^ {2} \ geq 2.3 y) \ wedge \ left (\ neg b \ vee y <-34,4 \ vee \ exp (x)> {y \ over x} \ right) \ end {array}}}

kde

{\ displaystyle b \ in {\ mathbb {B}}, x, y \ in {\ mathbb {R}}}

je uspokojivý. Pak se takové problémy stanou obecně nerozhodnutelnými . (Teorie reálných uzavřených polí , a tedy celá teorie reálných čísel prvního řádu , je však rozhodnutelná pomocí eliminace kvantifikátoru . Je to způsobeno Alfredem Tarskim .) Teorie prvního řádu přirozených čísel sčítáním (ale ne násobením) , nazývaný Presburgerova aritmetika , je také rozhodnutelný. Vzhledem k tomu, že násobení konstantami lze implementovat jako vnořené dodatky, lze aritmetiku v mnoha počítačových programech vyjádřit pomocí Presburgerovy aritmetiky, což vede k rozhodnutelným vzorcům.

Příklady řešitelů SMT, kteří se zabývají booleovskými kombinacemi atomů teorie z nerozhodnutelných aritmetických teorií nad reálnými, jsou ABsolver, který využívá klasickou architekturu DPLL (T) s nelineárním optimalizačním paketem jako (nutně neúplný) podřízený řešitel teorie a iSAT , staví sjednocení řešení DPLL SAT a šíření intervalových omezení nazývané algoritmus iSAT.

Řešitelé

Níže uvedená tabulka shrnuje některé funkce mnoha dostupných řešičů SMT. Sloupec „SMT-LIB“ označuje kompatibilitu s jazykem SMT-LIB; mnoho systémů označených jako „ano“ může podporovat pouze starší verze SMT-LIB nebo nabízí jazyk pouze částečnou podporu. Sloupec „CVC“ označuje podporu pro jazyk CVC. Sloupec „DIMACS“ označuje podporu formátu DIMACS .

Projekty se liší nejen funkcemi a výkonem, ale také životaschopností okolní komunity, jejím trvalým zájmem o projekt a schopností přispívat dokumentací, opravami, testy a vylepšeními.

Plošina			Funkce						Poznámky
název	OS	Licence	SMT-LIB	CVC	DIMACY	Integrované teorie	API	SMT-COMP [1]
ABsolver	Linux	CPL	v1.2	Ne	Ano	lineární aritmetický, nelineární aritmetický	C ++	Ne	Založené na DPLL
Alt-Ergo	Linux , Mac OS , Windows	CeCILL-C (zhruba ekvivalent LGPL )	parciální v1.2 a v2.0	Ne	Ne	prázdná teorie , lineární celé číslo a racionální aritmetika, nelineární aritmetika, polymorfní pole , vyjmenované datové typy , AC symboly , bitvektory , záznam datových typů , kvantifikátory	OCaml	2008	Polymorfní vstupní jazyk prvního řádu à la ML, založený na SAT-solveru, kombinuje přístupy podobné Shostakovi a Nelson-Oppen pro uvažování o modulo teoriích
Barcelogic	Linux	Proprietární	v1.2			prázdná teorie , diferenční logika	C ++	2009	Uzavření kongruence založené na DPLL
Bobr	Linux , Windows	BSD	v1.2	Ne	Ne	bitvektory	OCaml	2009	SAT-solver založený
Boolektor	Linux	MIT	v1.2	Ne	Ne	bitvektory , pole	C	2009	SAT-solver založený
CVC3	Linux	BSD	v1.2	Ano		prázdná teorie , lineární aritmetika, pole, n-tice, typy, záznamy, bitvektory, kvantifikátory	C / C ++	2010	kontrolní výstup do HOL
CVC4	Linux , Mac OS , Windows , FreeBSD	BSD	Ano	Ano		racionální a celočíselná lineární aritmetika, pole, n-tice, záznamy, indukční datové typy, bitvektory, řetězce a rovnost nad neinterpretovanými funkčními symboly	C ++	2010	verze 1.5 vydaná v červenci 2017
Sada nástrojů pro rozhodovací postup (DPT)	Linux	Apache	Ne				OCaml	Ne	Založené na DPLL
iSAT	Linux	Proprietární	Ne			nelineární aritmetika		Ne	Založené na DPLL
MathSAT	Linux , Mac OS , Windows	Proprietární	Ano		Ano	prázdná teorie , lineární aritmetika, nelineární aritmetika, bitvektory, pole	C / C ++ , Python , Java	2010	Založené na DPLL
MiniSmt	Linux	LGPL	částečný v2.0			nelineární aritmetika		2010	SAT-solver, Yices
Norn									Řešitel SMT pro omezení řetězců
OpenCog	Linux	AGPL	Ne	Ne	Ne	pravděpodobnostní logika , aritmetika. relační modely	C ++ , schéma , Python	Ne	podgraf izomorfismus
OpenSMT	Linux , Mac OS , Windows	GPLv3	částečný v2.0		Ano	prázdná teorie , rozdíly, lineární aritmetika, bitvektory	C ++	2011	líný řešič SMT
raSAT	Linux	GPLv3	v2.0			reálná a celočíselná nelineární aritmetika		2014, 2015	rozšíření propagace Interval Constraint o testování a teorém střední hodnoty
Satén	?	Proprietární	v1.2			lineární aritmetika, diferenční logika	žádný	2009
SMTInterpol	Linux , Mac OS , Windows	LGPLv3	v2.5			neinterpretované funkce, lineární reálná aritmetika a lineární celé číslo aritmetika	Jáva	2012	Zaměřuje se na generování vysoce kvalitních, kompaktních interpolantů.
SMCHR	Linux , Mac OS , Windows	GPLv3	Ne	Ne	Ne	lineární aritmetický, nelineární aritmetický, hromady	C	Ne	Může implementovat nové teorie pomocí pravidel zpracování omezení .
SMT-RAT	Linux , Mac OS	MIT	v2.0	Ne	Ne	lineární aritmetický, nelineární aritmetický	C ++	2015	Sada nástrojů pro strategické a paralelní řešení SMT skládající se z kolekce implementací vyhovujících SMT.
SONOLAR	Linux , Windows	Proprietární	částečný v2.0			bitvektory	C	2010	SAT-solver založený
Kopí	Linux , Mac OS , Windows	Proprietární	v1.2			bitvektory		2008
STP	Linux , OpenBSD , Windows , Mac OS	MIT	částečný v2.0	Ano	Ne	bitvektory, pole	C , C ++ , Python , OCaml , Java	2011	SAT-solver založený
MEČ	Linux	Proprietární	v1.2			bitvektory		2009
UCLID	Linux	BSD	Ne	Ne	Ne	prázdná teorie , lineární aritmetika, bitvektory a omezená lambda (pole, paměti, mezipaměť atd.)		Ne	Založeno na řešení SAT, napsáno v Moskvě ML . Vstupním jazykem je kontrola modelu SMV. Dobře zdokumentované!
veriT	Linux , OS X	BSD	částečný v2.0			prázdná teorie , racionální a celočíselná lineární aritmetika, kvantifikátory a rovnost nad neinterpretovanými funkčními symboly	C / C ++	2010	SAT-solver založený
Yices	Linux , Mac OS , Windows , FreeBSD	GPLv3	v2.0	Ne	Ano	racionální a celočíselná lineární aritmetika, bitvektory, pole a rovnost nad neinterpretovanými funkčními symboly	C	2014	Zdrojový kód je k dispozici online
Poskytovatel věty Z3	Linux , Mac OS , Windows , FreeBSD	MIT	v2.0		Ano	prázdná teorie , lineární aritmetika, nelineární aritmetika, bitvektory, pole, datové typy, kvantifikátory , řetězce	C / C ++ , .NET , OCaml , Python , Java , Haskell	2011	Zdrojový kód je k dispozici online

Standardizace a soutěž řešitelů SMT-COMP

Existuje několik pokusů popsat standardizované rozhraní pro řešitele SMT (a automatizované prověrky teorémů , termín často používaný jako synonymum). Nejvýznamnějším je standard SMT-LIB, který poskytuje jazyk založený na S-výrazech . Mezi další standardizované formáty, které jsou běžně podporovány, patří formát DIMACS podporovaný mnoha booleovskými řešiteli SAT a formát CVC používaný automatickým ověřovacím teorem CVC.

Formát SMT-LIB také přichází s řadou standardizovaných měřítek a umožnil každoroční soutěž mezi řešiteli SMT s názvem SMT-COMP. Soutěž se původně konala během konference Computer Aided Verification Conference (CAV), ale od roku 2020 je soutěž pořádána jako součást SMT Workshopu, který je přidružen k Mezinárodní společné konferenci o automatizovaném uvažování (IJCAR).

Aplikace

Řešitelé SMT jsou užiteční jak pro ověřování, ověřování správnosti programů, testování softwaru na základě symbolického provádění , tak pro syntézu , generování fragmentů programů prohledáváním prostoru možných programů. Kromě verifikace softwaru se řešitelé SMT používají také pro odvozování typů a pro modelování teoretických scénářů, včetně přesvědčení modelových aktérů v řízení jaderných zbraní .

Ověření

Počítačem podporované ověřování počítačových programů často používá řešení SMT. Běžnou technikou je převést předpoklady, postkondice, podmínky smyčky a tvrzení do vzorců SMT, aby se zjistilo, zda všechny vlastnosti mohou držet.

Na řešiči Z3 SMT je postaveno mnoho ověřovatelů . Boogie je jazyk pro střední ověřování, který používá Z3 k automatické kontrole jednoduchých imperativních programů. VCC ověřovatel pro souběžné C používá Boogie, stejně jako Dafny naléhavých objektově založené na programech, Kalich souběžných programů a Spec # pro C #. F * je jazyk závislý na typu, který používá Z3 k vyhledání důkazů; kompilátor tyto důkazy přenáší, aby vytvořil bajtový kód nesoucí důkaz. Ověření Viper infrastruktura zakóduje ověřovací podmínky pro Z3. SBV knihovna poskytuje SMT-založené ověření programů Haskell, a umožňuje uživateli vybrat z několika řešitelů, jako Z3, ABC, Boolector, CVC4 , MathSAT a Yices.

Na vrcholu řešiče Alt-Ergo SMT je také mnoho ověřovatelů . Zde je seznam vyspělých aplikací:

Why3 , platforma pro deduktivní ověření programu, používá Alt-Ergo jako svůj hlavní prover;
CAVEAT, ověřovatel C vyvinutý společností CEA a používaný společností Airbus; Alt-Ergo byl zařazen do kvalifikace DO-178C jednoho ze svých nedávných letadel;
Frama-C , rámec pro analýzu C-kódu, používá Alt-Ergo v zásuvných modulech Jessie a WP (vyhrazeno pro „deduktivní ověření programu“);
SPARK používá CVC4 a Alt-Ergo (za GNATprove) k automatizaci ověření některých tvrzení v SPARKu 2014;
Atelier-B může použít Alt-Ergo místo svého hlavního proveru (zvýšení úspěšnosti z 84% na 98% v benchmarcích projektu ANR Bware );
Rodin , rámec metody B vyvinutý společností Systerel, může používat Alt-Ergo jako back-end;
Skříň , open source model checker pro ověřování bezpečnostních vlastností přechodových systémů založených na poli.
EasyCrypt , sada nástrojů pro uvažování o relačních vlastnostech pravděpodobnostních výpočtů s kontradiktorním kódem.

Mnoho řešitelů SMT implementuje běžný formát rozhraní s názvem SMTLIB2 (takové soubory mají obvykle příponu „ .smt2 “). Nástroj LiquidHaskell implementuje ověřovatel založený na typu zdokonalení pro Haskell, který může použít jakýkoli řešič vyhovující SMTLIB2, např. CVC4, MathSat nebo Z3.

Analýza a testování založené na symbolickém provádění

Důležitou aplikací řešičů SMT je symbolické provádění pro analýzu a testování programů (např. Concolic testování ), zaměřené zejména na hledání bezpečnostních slabin. Důležité aktivně udržované stroje v této kategorii zahrnují SAGE z Microsoft Research , Klee , S2E a Triton . Řešiče SMT, které jsou zvláště užitečné pro aplikace symbolického provádění, zahrnují Z3 , STP , Z3str2 a Boolector .

Viz také

Poznámky

^ Barbosa, Haniel a kol. " Rozšíření řešičů SMT na logiku vyššího řádu ." Mezinárodní konference o automatizovaném odpočtu. Springer, Cham, 2019.
^ Nieuwenhuis, R .; Oliveras, A .; Tinelli, C. (2006), „Řešení SAT a SAT modulárních teorií: Od abstraktního postupu Davis-Putnam-Logemann-Loveland k DPLL (T)“, Journal of the ACM (PDF) , 53 , pp. 937–977
^ Bauer, A .; Pister, M .; Tautschnig, M. (2007), „Podpora nástrojů pro analýzu hybridních systémů a modelů“, Sborník konference z roku 2007 o konstrukci, automatizaci a testování v Evropě (DATE'07) , IEEE Computer Society, s. 1, CiteSeerX 10.1.1.323.6807 , doi : 10.1109 / DATE.2007.364411 , ISBN 978-3-9810801-2-4, S2CID 9159847
^ Fränzle, M .; Herde, C .; Ratschan, S .; Schubert, T .; Teige, T. (2007), „Efektivní řešení velkých nelineárních aritmetických omezovacích systémů se složitou booleovskou strukturou“, zvláštní vydání JSAT o integraci SAT / CP (PDF) , 1 , s. 209–236
^ Barrett, Clark; de Moura, Leonardo; Stump, Aaron (2005). Etessami, Kousha; Rajamani, Sriram K. (eds.). „SMT-COMP: Soutěž o uspokojení modulárních teorií“ . Ověření pomocí počítače . Přednášky z informatiky. Berlín, Heidelberg: Springer: 20–23. doi : 10,1007 / 11513988_4 . ISBN 978-3-540-31686-2.
^ Barrett, Clark; de Moura, Leonardo; Ranise, Silvio; Pařez, Aarone; Tinelli, Cesare (2011). Barner, Sharon; Harris, Ian; Kroening, Daniel; Raz, Orna (eds.). „Iniciativa SMT-LIB a vzestup SMT“ . Hardware a software: Ověření a testování . Přednášky z informatiky. Berlín, Heidelberg: Springer: 3–3. doi : 10.1007 / 978-3-642-19583-9_2 . ISBN 978-3-642-19583-9.
^ „SMT-COMP 2020“ . SMT-COMP . Citováno 2020-10-19 .
^ Hassan, Mostafa a kol. "Odvození typu založené na Maxsmt pro python 3." Mezinárodní konference o ověřování pomocí počítače. Springer, Cham, 2018.
^ Loncaric, Calvin a kol. "Praktický rámec pro vysvětlení chyby odvození typu." Oznámení ACM SIGPLAN 51.10 (2016): 781-799.
^ Beaumont, Paul; Evans, Neil; Huth, Michael; Plant, Tom (2015). Pernul, Günther; YA Ryan, Peter; Weippl, Edgar (eds.). "Analýza spolehlivosti pro kontrolu jaderných zbraní: SMT abstrakce Bayesian Belief Networks" . Počítačová bezpečnost - ESORICS 2015 . Přednášky z informatiky. Cham: Springer International Publishing: 521–540. doi : 10.1007 / 978-3-319-24174-6_27 . ISBN 978-3-319-24174-6.

Reference

C Barrett, R Sebastiani, S Seshia a C Tinelli, „ teorie uspokojivosti modulo “. V Handbook of Satisfiability, sv. 185 of Frontiers in Artificial Intelligence and Applications, (A Biere, MJH Heule, H van Maaren a T Walsh, eds.), IOS Press, únor 2009, str. 825–885.
Vijay Ganesh (PhD. Thesis 2007), Decision Procedures for Bit-Vectors, Arrays and Integers , Computer Science Department, Stanford University, Stanford, CA, USA, září 2007
Susmit Jha, Rhishikesh Limaye a Sanjit A. Seshia. Beaver: Inženýrství efektivního řešení SMT pro aritmetiku bitových vektorů. In Proceedings of 21st International Conference on Computer-Aided Verification, pp. 668–674, 2009.
RE Bryant, SM German a MN Velev, „ Ověření mikroprocesoru pomocí efektivních rozhodovacích postupů pro logiku rovnosti s neinterpretovanými funkcemi “, v Analytické tablo a související metody, s. 1–13, 1999.
M. Davis a H. Putnam, A Computing Procedure for Quantification Theory , Journal of the Association for Computing Machinery, sv. 7, č. 201, 215, 1960.
M. Davis, G. Logemann a D. Loveland, Strojový program pro ověřování teorém , komunikace ACM, sv. 5, č. 7, str. 394–397, 1962.
D. Kroening a O. Strichman, Rozhodovací procedury - algoritmické hledisko (2008), Springer (řada Teoretická informatika) ISBN 978-3-540-74104-6 .
G.-J. Nam, KA Sakallah a R. Rutenbar, nový přístup k podrobnému směrování FPGA prostřednictvím vyhledávací Boolean uspokojivosti , IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, sv. 21, č. 6, s. 674–684, 2002.
SMT-LIB: Knihovna teorií modulární teorie uspokojivosti
SMT-COMP: Soutěž o teorie uspokojitelnosti v modulárních teoriích
Rozhodovací postupy - algoritmické hledisko
R. Sebastiani, Lazy Satisfiability Modulo Theories , Dipartimento di Ingegneria e Scienza dell'Informazione, Universita di Trento, Itálie, prosinec 2007
D. Yurichev, Rychlý úvod do řešení SAT / SMT a symbolické provedení

Tento článek je převzat ze sloupce v elektronickém zpravodaji ACM SIGDA od profesora Karema Sakallaha . Původní text je k dispozici zde

[1] Barbosa, Haniel a kol. " Rozšíření řešičů SMT na logiku vyššího řádu ." Mezinárodní konference o automatizovaném odpočtu. Springer, Cham, 2019.

[2] Nieuwenhuis, R .; Oliveras, A .; Tinelli, C. (2006), „Řešení SAT a SAT modulárních teorií: Od abstraktního postupu Davis-Putnam-Logemann-Loveland k DPLL (T)“, Journal of the ACM (PDF) , 53 , pp. 937–977

[3] Bauer, A .; Pister, M .; Tautschnig, M. (2007), „Podpora nástrojů pro analýzu hybridních systémů a modelů“, Sborník konference z roku 2007 o konstrukci, automatizaci a testování v Evropě (DATE'07) , IEEE Computer Society, s. 1, CiteSeerX 10.1.1.323.6807 , doi : 10.1109 / DATE.2007.364411 , ISBN 978-3-9810801-2-4, S2CID 9159847

[4] Fränzle, M .; Herde, C .; Ratschan, S .; Schubert, T .; Teige, T. (2007), „Efektivní řešení velkých nelineárních aritmetických omezovacích systémů se složitou booleovskou strukturou“, zvláštní vydání JSAT o integraci SAT / CP (PDF) , 1 , s. 209–236

[5] Barrett, Clark; de Moura, Leonardo; Stump, Aaron (2005). Etessami, Kousha; Rajamani, Sriram K. (eds.). „SMT-COMP: Soutěž o uspokojení modulárních teorií“ . Ověření pomocí počítače . Přednášky z informatiky. Berlín, Heidelberg: Springer: 20–23. doi : 10,1007 / 11513988_4 . ISBN 978-3-540-31686-2.

[6] Barrett, Clark; de Moura, Leonardo; Ranise, Silvio; Pařez, Aarone; Tinelli, Cesare (2011). Barner, Sharon; Harris, Ian; Kroening, Daniel; Raz, Orna (eds.). „Iniciativa SMT-LIB a vzestup SMT“ . Hardware a software: Ověření a testování . Přednášky z informatiky. Berlín, Heidelberg: Springer: 3–3. doi : 10.1007 / 978-3-642-19583-9_2 . ISBN 978-3-642-19583-9.

[7] „SMT-COMP 2020“ . SMT-COMP . Citováno 2020-10-19 .

[8] Hassan, Mostafa a kol. "Odvození typu založené na Maxsmt pro python 3." Mezinárodní konference o ověřování pomocí počítače. Springer, Cham, 2018.

[9] Loncaric, Calvin a kol. "Praktický rámec pro vysvětlení chyby odvození typu." Oznámení ACM SIGPLAN 51.10 (2016): 781-799.

[10] Beaumont, Paul; Evans, Neil; Huth, Michael; Plant, Tom (2015). Pernul, Günther; YA Ryan, Peter; Weippl, Edgar (eds.). "Analýza spolehlivosti pro kontrolu jaderných zbraní: SMT abstrakce Bayesian Belief Networks" . Počítačová bezpečnost - ESORICS 2015 . Přednášky z informatiky. Cham: Springer International Publishing: 521–540. doi : 10.1007 / 978-3-319-24174-6_27 . ISBN 978-3-319-24174-6.

Languages

In other projects