Efficient Satisfiability Modulo Theories via Delayed Theory Combination
Identifieur interne : 000F23 ( Istex/Curation ); précédent : 000F22; suivant : 000F24Efficient Satisfiability Modulo Theories via Delayed Theory Combination
Auteurs : Marco Bozzano [Italie] ; Roberto Bruttomesso [Italie] ; Alessandro Cimatti [Italie] ; Tommi Junttila [Finlande] ; Silvio Ranise [France] ; Peter Van Rossum [Pays-Bas] ; Roberto Sebastiani [Italie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: The problem of deciding the satisfiability of a quantifier-free formula with respect to a background theory, also known as Satisfiability Modulo Theories (SMT), is gaining increasing relevance in verification: representation capabilities beyond propositional logic allow for a natural modeling of real-world problems (e.g., pipeline and RTL circuits verification, proof obligations in software systems). In this paper, we focus on the case where the background theory is the combination T 1∪T 2 of two simpler theories. Many SMT procedures combine a boolean model enumeration with a decision procedure for T 1∪T 2, where conjunctions of literals can be decided by an integration schema such as Nelson-Oppen, via a structured exchange of interface formulae (e.g., equalities in the case of convex theories, disjunctions of equalities otherwise). We propose a new approach for SMT(T 1∪T 2), called Delayed Theory Combination, which does not require a decision procedure for T 1∪T 2, but only individual decision procedures for T 1 and T 2, which are directly integrated into the boolean model enumerator. This approach is much simpler and natural, allows each of the solvers to be implemented and optimized without taking into account the others, and it nicely encompasses the case of non-convex theories. We show the effectiveness of the approach by a thorough experimental comparison.
Url:
DOI: 10.1007/11513988_34
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000F37
Links to Exploration step
ISTEX:413EE9A4C2AFD16BD40056910219928802E51CDALe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient Satisfiability Modulo Theories via Delayed Theory Combination</title>
<author><name sortKey="Bozzano, Marco" sort="Bozzano, Marco" uniqKey="Bozzano M" first="Marco" last="Bozzano">Marco Bozzano</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bozzano@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Bruttomesso, Roberto" sort="Bruttomesso, Roberto" uniqKey="Bruttomesso R" first="Roberto" last="Bruttomesso">Roberto Bruttomesso</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bruttomesso@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Cimatti, Alessandro" sort="Cimatti, Alessandro" uniqKey="Cimatti A" first="Alessandro" last="Cimatti">Alessandro Cimatti</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: cimatti@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Junttila, Tommi" sort="Junttila, Tommi" uniqKey="Junttila T" first="Tommi" last="Junttila">Tommi Junttila</name>
<affiliation wicri:level="1"><mods:affiliation>Helsinki University of Technology, Finland</mods:affiliation>
<country xml:lang="fr">Finlande</country>
<wicri:regionArea>Helsinki University of Technology</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Tommi.Junttila@tkk.fi</mods:affiliation>
<country wicri:rule="url">Finlande</country>
</affiliation>
</author>
<author><name sortKey="Ranise, Silvio" sort="Ranise, Silvio" uniqKey="Ranise S" first="Silvio" last="Ranise">Silvio Ranise</name>
<affiliation wicri:level="1"><mods:affiliation>LORIA and INRIA-Lorraine, Villers les Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA and INRIA-Lorraine, Villers les Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Silvio.Ranise@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Van Rossum, Peter" sort="Van Rossum, Peter" uniqKey="Van Rossum P" first="Peter" last="Van Rossum">Peter Van Rossum</name>
<affiliation wicri:level="1"><mods:affiliation>Radboud University, Nijmegen, The Netherlands</mods:affiliation>
<country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>Radboud University, Nijmegen</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: petervr@sci.kun.nl</mods:affiliation>
<country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Sebastiani, Roberto" sort="Sebastiani, Roberto" uniqKey="Sebastiani R" first="Roberto" last="Sebastiani">Roberto Sebastiani</name>
<affiliation wicri:level="1"><mods:affiliation>DIT, Università di Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>DIT, Università di Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: roberto.sebastiani@unitn.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:413EE9A4C2AFD16BD40056910219928802E51CDA</idno>
<date when="2005" year="2005">2005</date>
<idno type="doi">10.1007/11513988_34</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-TR9Z5WSX-Q/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">000F37</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000F37</idno>
<idno type="wicri:Area/Istex/Curation">000F23</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Efficient Satisfiability Modulo Theories via Delayed Theory Combination</title>
<author><name sortKey="Bozzano, Marco" sort="Bozzano, Marco" uniqKey="Bozzano M" first="Marco" last="Bozzano">Marco Bozzano</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bozzano@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Bruttomesso, Roberto" sort="Bruttomesso, Roberto" uniqKey="Bruttomesso R" first="Roberto" last="Bruttomesso">Roberto Bruttomesso</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: bruttomesso@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Cimatti, Alessandro" sort="Cimatti, Alessandro" uniqKey="Cimatti A" first="Alessandro" last="Cimatti">Alessandro Cimatti</name>
<affiliation wicri:level="1"><mods:affiliation>ITC-IRST, Povo, Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>ITC-IRST, Povo, Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: cimatti@itc.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
<author><name sortKey="Junttila, Tommi" sort="Junttila, Tommi" uniqKey="Junttila T" first="Tommi" last="Junttila">Tommi Junttila</name>
<affiliation wicri:level="1"><mods:affiliation>Helsinki University of Technology, Finland</mods:affiliation>
<country xml:lang="fr">Finlande</country>
<wicri:regionArea>Helsinki University of Technology</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Tommi.Junttila@tkk.fi</mods:affiliation>
<country wicri:rule="url">Finlande</country>
</affiliation>
</author>
<author><name sortKey="Ranise, Silvio" sort="Ranise, Silvio" uniqKey="Ranise S" first="Silvio" last="Ranise">Silvio Ranise</name>
<affiliation wicri:level="1"><mods:affiliation>LORIA and INRIA-Lorraine, Villers les Nancy, France</mods:affiliation>
<country xml:lang="fr">France</country>
<wicri:regionArea>LORIA and INRIA-Lorraine, Villers les Nancy</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: Silvio.Ranise@loria.fr</mods:affiliation>
<country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Van Rossum, Peter" sort="Van Rossum, Peter" uniqKey="Van Rossum P" first="Peter" last="Van Rossum">Peter Van Rossum</name>
<affiliation wicri:level="1"><mods:affiliation>Radboud University, Nijmegen, The Netherlands</mods:affiliation>
<country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>Radboud University, Nijmegen</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: petervr@sci.kun.nl</mods:affiliation>
<country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Sebastiani, Roberto" sort="Sebastiani, Roberto" uniqKey="Sebastiani R" first="Roberto" last="Sebastiani">Roberto Sebastiani</name>
<affiliation wicri:level="1"><mods:affiliation>DIT, Università di Trento, Italy</mods:affiliation>
<country xml:lang="fr">Italie</country>
<wicri:regionArea>DIT, Università di Trento</wicri:regionArea>
</affiliation>
<affiliation wicri:level="1"><mods:affiliation>E-mail: roberto.sebastiani@unitn.it</mods:affiliation>
<country wicri:rule="url">Italie</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: The problem of deciding the satisfiability of a quantifier-free formula with respect to a background theory, also known as Satisfiability Modulo Theories (SMT), is gaining increasing relevance in verification: representation capabilities beyond propositional logic allow for a natural modeling of real-world problems (e.g., pipeline and RTL circuits verification, proof obligations in software systems). In this paper, we focus on the case where the background theory is the combination T 1∪T 2 of two simpler theories. Many SMT procedures combine a boolean model enumeration with a decision procedure for T 1∪T 2, where conjunctions of literals can be decided by an integration schema such as Nelson-Oppen, via a structured exchange of interface formulae (e.g., equalities in the case of convex theories, disjunctions of equalities otherwise). We propose a new approach for SMT(T 1∪T 2), called Delayed Theory Combination, which does not require a decision procedure for T 1∪T 2, but only individual decision procedures for T 1 and T 2, which are directly integrated into the boolean model enumerator. This approach is much simpler and natural, allows each of the solvers to be implemented and optimized without taking into account the others, and it nicely encompasses the case of non-convex theories. We show the effectiveness of the approach by a thorough experimental comparison.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Istex/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000F23 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Curation/biblio.hfd -nk 000F23 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Istex |étape= Curation |type= RBID |clé= ISTEX:413EE9A4C2AFD16BD40056910219928802E51CDA |texte= Efficient Satisfiability Modulo Theories via Delayed Theory Combination }}
This area was generated with Dilib version V0.6.33. |