| dc.contributor | Saubion, Frédéric | |
| dc.contributor | Castro Valdebenito, Carlos | |
| dc.contributor | Monfroy, Eric | |
| dc.contributor | UNIVERSIDAD TECNICA FEDERICO SANTA MARIA | |
| dc.creator | Gálvez Ramírez, Nicolás Sebastián | |
| dc.date | 2022-03-10T12:45:34Z | |
| dc.date | 2022-08-16T18:42:11Z | |
| dc.date | 2022-03-10T12:45:34Z | |
| dc.date | 2022-08-16T18:42:11Z | |
| dc.date | 2018 | |
| dc.date.accessioned | 2023-08-22T04:16:43Z | |
| dc.date.available | 2023-08-22T04:16:43Z | |
| dc.identifier | 21130089 | |
| dc.identifier | https://hdl.handle.net/10533/253180 | |
| dc.identifier.uri | https://repositorioslatinoamericanos.uchile.cl/handle/2250/8318862 | |
| dc.description | The Strategy Challenge in Satisfiability Modulo Theories (SMT) claims to build theoretical and practical tools allowing users to exert strategic control over core heuristic aspects of high-performance SMT solvers. In this work, we focus on Z3 Theorem Prover: one of the most efficient SMT solvers according to the SMT Competition, SMT-COMP. In SMT solvers, the definition of a strategy relies on a set of tools that can be scheduled and configured in order to guide the search for a (un)satisfiability proof of a given instance. Given these concepts, this challenge could be seen as:
• Artificial Intelligence topic, building an algorithm selection procedure to select and order heuristics components to improve SMT solver performance.
• Automated Deduction topic, aiming to build more efficient and robust theorem proving solvers.
• Search-Based Software Engineering (SBSE) topic, improving SMT software performance by generating a practical tool to manage its own critical code. And also enhancing the resolution of several SBSE problems which are commonly mapped as SMT instances.
In this thesis, we address the Strategy Challenge in SMT defining a framework for the autonomous generation of strategies in Z3, i.e., a practical system to automatically generate SMT strategies without the use of expert knowledge. This framework is applied through an incremental evolutionary approach starting from basic algorithms to more complex genetic constructions. The steps include the following:
1. A set of one-task algorithms for SMT strategies:
• A simple Parameter Tuner for SMT Strategies (StraTUNE).
• A simple Evolutionary Strategy Generator (StratGEN), a skeleton-based evolutionary algorithm to generate SMT strategies.
2. StratEVO, a Tree-based Genetic Programming algorithm that generates complex SMT strategies.
3. A set of cooperative algorithms:
• SequencEVO, an off-line sequential cooperative algorithm between StratEVO and StraTUNE.
• HybridEVO, a set of StratEVO variations, which used different online cooperative schemes.
4. ExpandEVO, a variety of algorithms that includes time expansion rules in order to generate strategies semantically valid for hard solving contexts.
This framework formalises strategies modification as rewriting rules, where algorithms act as engines to apply them. This intermediate layer will allow applying any algorithm or operator with no need to be structurally modified, in order to introduce new information in strategies. Validation is done through experiments on classic benchmarks of the SMT-COMP. | |
| dc.format | application/pdf | |
| dc.relation | instname: Conicyt | |
| dc.relation | reponame: Repositorio Digital RI2.0 | |
| dc.relation | info:eu-repo/grantAgreement//21130089 | |
| dc.relation | info:eu-repo/semantics/dataset/hdl.handle.net/10533/93488 | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 Chile | |
| dc.rights | info:eu-repo/semantics/openAccess | |
| dc.rights | http://creativecommons.org/licenses/by-nc-nd/3.0/cl/ | |
| dc.subject | Ingeniería y Tecnología | |
| dc.subject | Ingeniería Eléctrica, Ingeniería Electrónica, Informática | |
| dc.title | A framework for autonomous generation of strategies in satisfiability modulo theories | |
| dc.type | info:eu-repo/semantics/doctoralThesis | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
| dc.type | Tesis | |
