Teorías de satisfacibilidad módulo

Problema lógico estudiado en informática.

En informática y lógica matemática , las teorías de satisfacibilidad módulo ( SMT ) son el problema de determinar si una fórmula matemática es satisfacible . Generaliza el problema de satisfacibilidad booleano (SAT) a fórmulas más complejas que involucran números reales , enteros y/o varias estructuras de datos como listas , matrices , vectores de bits y cadenas . El nombre se deriva del hecho de que estas expresiones se interpretan dentro de ("módulo") una cierta teoría formal en lógica de primer orden con igualdad (a menudo no permitiendo cuantificadores ). Los solucionadores SMT son herramientas que tienen como objetivo resolver el problema SMT para un subconjunto práctico de entradas. Los solucionadores SMT como Z3 y cvc5 se han utilizado como un bloque de construcción para una amplia gama de aplicaciones en informática, incluida la demostración automatizada de teoremas , el análisis de programas , la verificación de programas y las pruebas de software .

Dado que la satisfacibilidad booleana ya es NP-completa , el problema SMT es típicamente NP-duro y para muchas teorías es indecidible . Los investigadores estudian qué teorías o subconjuntos de teorías conducen a un problema SMT decidible y la complejidad computacional de los casos decidibles. Los procedimientos de decisión resultantes a menudo se implementan directamente en los solucionadores SMT; véase, por ejemplo, la decidibilidad de la aritmética de Presburger . El SMT puede considerarse como un problema de satisfacción de restricciones y, por lo tanto, un cierto enfoque formalizado para la programación de restricciones .

Terminología y ejemplos

Formalmente hablando, una instancia de SMT es una fórmula en lógica de primer orden , donde algunos símbolos de función y predicado tienen interpretaciones adicionales, y SMT es el problema de determinar si dicha fórmula es satisfacible. En otras palabras, imagine una instancia del problema de satisfacibilidad booleana (SAT) en el que algunas de las variables binarias se reemplazan por predicados sobre un conjunto adecuado de variables no binarias. Un predicado es una función de valor binario de variables no binarias. Los predicados de ejemplo incluyen desigualdades lineales (p. ej., ) o igualdades que involucran términos no interpretados y símbolos de función (p. ej., donde es alguna función no especificada de dos argumentos). Estos predicados se clasifican de acuerdo con cada teoría respectiva asignada. Por ejemplo, las desigualdades lineales sobre variables reales se evalúan utilizando las reglas de la teoría de la aritmética real lineal , mientras que los predicados que involucran términos no interpretados y símbolos de función se evalúan utilizando las reglas de la teoría de funciones no interpretadas con igualdad (a veces denominada teoría vacía ). Otras teorías incluyen las teorías de matrices y estructuras de listas (útiles para modelar y verificar programas informáticos ) y la teoría de vectores de bits (útil para modelar y verificar diseños de hardware ). También son posibles las subteorías: por ejemplo, la lógica diferencial es una subteoría de la aritmética lineal en la que cada desigualdad está restringida a tener la forma para variables y y constantes . ${\displaystyle 3x+2y-z\geq 4}$ ${\displaystyle f(f(u,v),v)=f(u,v)}$ ${\displaystyle f}$ ${\displaystyle x-y>c}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle c}$

Los ejemplos anteriores muestran el uso de la aritmética lineal de números enteros en desigualdades. Otros ejemplos incluyen:

• Satisfacción: Determinar si es satisfacible. ${\displaystyle x\vee (y\wedge \neg z)}$
• Acceso a la matriz: busque un valor para la matriz A tal que A[0]=5.
• Aritmética de vectores de bits: determinar si x e y son números distintos de 3 bits.
• Funciones no interpretadas: Encuentra valores para x e y tales que y . ${\displaystyle f(x)=2}$ ${\displaystyle g(x)=3}$

La mayoría de los solucionadores SMT solo admiten fragmentos de su lógica sin cuantificadores . ^{[ cita requerida ]}

Relación con la demostración automática de teoremas

Existe una superposición sustancial entre la resolución de problemas SMT y la demostración automatizada de teoremas (ATP). En general, los probadores automáticos de teoremas se centran en respaldar la lógica de primer orden completa con cuantificadores, mientras que los solucionadores SMT se centran más en respaldar varias teorías (símbolos de predicado interpretados). Los ATP se destacan en problemas con muchos cuantificadores, mientras que los solucionadores SMT funcionan bien en problemas grandes sin cuantificadores. ^[1] La línea es lo suficientemente borrosa como para que algunos ATP participen en SMT-COMP, mientras que algunos solucionadores SMT participen en CASC . ^[2]

Poder expresivo

Una instancia SMT es una generalización de una instancia SAT booleana en la que se reemplazan varios conjuntos de variables por predicados de una variedad de teorías subyacentes. Las fórmulas SMT proporcionan un lenguaje de modelado mucho más rico que el que es posible con las fórmulas SAT booleanas. Por ejemplo, una fórmula SMT permite modelar las operaciones de ruta de datos de un microprocesador a nivel de palabra en lugar de a nivel de bit.

En comparación, la programación de conjuntos de respuestas también se basa en predicados (más precisamente, en oraciones atómicas creadas a partir de fórmulas atómicas ). A diferencia de la SMT, los programas de conjuntos de respuestas no tienen cuantificadores y no pueden expresar fácilmente restricciones como la aritmética lineal o la lógica diferencial; la programación de conjuntos de respuestas es más adecuada para problemas booleanos que se reducen a la teoría libre de funciones no interpretadas. La implementación de números enteros de 32 bits como vectores de bits en la programación de conjuntos de respuestas sufre la mayoría de los mismos problemas que enfrentaron los primeros solucionadores de SMT: las identidades "obvias" como x + y = y + x son difíciles de deducir.

La programación lógica de restricciones proporciona soporte para restricciones aritméticas lineales, pero dentro de un marco teórico completamente diferente. ^{[ cita requerida ]} Los solucionadores SMT también se han ampliado para resolver fórmulas en lógica de orden superior . ^[3]

Enfoques del solucionador

Los primeros intentos de resolver instancias de SMT implicaban traducirlas a instancias de SAT booleanas (por ejemplo, una variable entera de 32 bits se codificaría con 32 variables de un solo bit con pesos apropiados y las operaciones de nivel de palabra como "más" se reemplazarían por operaciones lógicas de nivel inferior en los bits) y pasar esta fórmula a un solucionador de SAT booleano. Este enfoque, que se conoce como enfoque ansioso ( o bitblasting ), tiene sus méritos: al preprocesar la fórmula de SMT en una fórmula SAT booleana equivalente, los solucionadores de SAT booleanos existentes se pueden usar "tal como están" y sus mejoras de rendimiento y capacidad se pueden aprovechar con el tiempo. Por otra parte, la pérdida de la semántica de alto nivel de las teorías subyacentes significa que el solucionador SAT booleano tiene que trabajar mucho más de lo necesario para descubrir hechos "obvios" (como la suma de números enteros). Esta observación condujo al desarrollo de una serie de solucionadores SMT que integran estrechamente el razonamiento booleano de una búsqueda de estilo DPLL con solucionadores específicos de la teoría ( T-solvers ) que manejan conjunciones (AND) de predicados de una teoría dada. Este enfoque se conoce como el enfoque perezoso . ^[4] ${\displaystyle x+y=y+x}$

Esta arquitectura, denominada DPLL(T) , ^[5] otorga la responsabilidad del razonamiento booleano al solucionador SAT basado en DPLL, que, a su vez, interactúa con un solucionador de la teoría T a través de una interfaz bien definida. El solucionador de la teoría solo necesita preocuparse por verificar la viabilidad de las conjunciones de predicados de teoría que le pasan desde el solucionador SAT mientras explora el espacio de búsqueda booleano de la fórmula. Sin embargo, para que esta integración funcione bien, el solucionador de la teoría debe poder participar en el análisis de propagación y conflicto, es decir, debe poder inferir nuevos hechos a partir de hechos ya establecidos, así como proporcionar explicaciones sucintas de la inviabilidad cuando surgen conflictos de teoría. En otras palabras, el solucionador de la teoría debe ser incremental y retrocedible .

Teorías decidibles

Los investigadores estudian qué teorías o subconjuntos de teorías conducen a un problema de lógica de primer orden decidible y la complejidad computacional de los casos decidibles. Dado que la lógica de primer orden completa es solo semidecidible , una línea de investigación intenta encontrar procedimientos de decisión eficientes para fragmentos de lógica de primer orden, como la lógica proposicional efectiva . ^[6]

Otra línea de investigación implica el desarrollo de teorías decidibles especializadas , incluyendo aritmética lineal sobre racionales y enteros , vectores de bits de ancho fijo, ^[7] aritmética de punto flotante (a menudo implementada en solucionadores SMT a través de bit-blasting , es decir, reducción a vectores de bits), ^{[8] [9]} cadenas , ^[10] (co)-tipos de datos , ^[11] secuencias (usadas para modelar matrices dinámicas ), ^[12] conjuntos y relaciones finitos , ^{[13] [14]} lógica de separación , ^[15] campos finitos , ^[16] y funciones no interpretadas , entre otras.

Las teorías monótonas booleanas son una clase de teoría que respalda la propagación eficiente de teorías y el análisis de conflictos, lo que permite un uso práctico dentro de los solucionadores DPLL(T). ^[17] Las teorías monótonas solo admiten variables booleanas (booleano es el único tipo ), y todas sus funciones y predicados p obedecen al axioma

${\displaystyle p(\ldots ,b_{i-1},0,b_{i+1},\ldots )\implies p(\ldots ,b_{i-1},1,b_{i+1},\ldots )}$

Entre los ejemplos de teorías monótonas se incluyen la alcanzabilidad de gráficos , la detección de colisiones para envolturas convexas , los cortes mínimos y la lógica del árbol de cálculo . ^[18] Cada programa Datalog puede interpretarse como una teoría monótona. ^[19]

SMT para teorías indecidibles

La mayoría de los enfoques SMT comunes admiten teorías decidibles . Sin embargo, muchos sistemas del mundo real, como una aeronave y su comportamiento, solo se pueden modelar mediante aritmética no lineal sobre los números reales que involucran funciones trascendentales . Este hecho motiva una extensión del problema SMT a teorías no lineales, como determinar si la siguiente ecuación es satisfacible:

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

dónde

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

Sin embargo, estos problemas son indecidibles en general. (Por otra parte, la teoría de cuerpos reales cerrados y, por lo tanto, la teoría completa de primer orden de los números reales , son decidibles utilizando la eliminación de cuantificadores . Esto se debe a Alfred Tarski .) La teoría de primer orden de los números naturales con adición (pero no multiplicación), llamada aritmética de Presburger , también es decidible. Dado que la multiplicación por constantes se puede implementar como adiciones anidadas, la aritmética en muchos programas de computadora se puede expresar utilizando la aritmética de Presburger, lo que da como resultado fórmulas decidibles.

Ejemplos de solucionadores SMT que abordan combinaciones booleanas de átomos de teoría a partir de teorías aritméticas indecidibles sobre los números reales son ABsolver, ^[20] que emplea una arquitectura DPLL(T) clásica con un paquete de optimización no lineal como solucionador de teoría subordinada (necesariamente incompleto), iSAT, que se basa en una unificación de la resolución SAT de DPLL y la propagación de restricciones de intervalo denominada algoritmo iSAT, ^[21] y cvc5 . ^[22]

Solucionadores

La siguiente tabla resume algunas de las características de los numerosos solucionadores SMT disponibles. La columna "SMT-LIB" indica compatibilidad con el lenguaje SMT-LIB; muchos sistemas marcados como "sí" pueden admitir solo versiones anteriores de SMT-LIB o ofrecer solo compatibilidad parcial con el lenguaje. La columna "CVC" indica compatibilidad con el lenguaje CVC . La columna "DIMACS" indica compatibilidad con el formato DIMACS .

Los proyectos difieren no solo en características y rendimiento, sino también en la viabilidad de la comunidad circundante, su interés continuo en el proyecto y su capacidad para contribuir con documentación, correcciones, pruebas y mejoras.

Estandarización y la competencia entre los solucionadores SMT-COMP

Existen múltiples intentos de describir una interfaz estandarizada para los solucionadores SMT (y los demostradores automáticos de teoremas , un término que a menudo se usa como sinónimo). El más destacado es el estándar SMT-LIB, ^{[ cita requerida ]} que proporciona un lenguaje basado en expresiones S. Otros formatos estandarizados comúnmente admitidos son el formato DIMACS ^{[ cita requerida ]} compatible con muchos solucionadores SAT booleanos y el formato CVC ^{[ cita requerida ]} utilizado por el demostrador automático de teoremas CVC.

El formato SMT-LIB también viene con una serie de puntos de referencia estandarizados y ha permitido una competencia anual entre solucionadores de SMT llamada SMT-COMP. Inicialmente, la competencia se llevó a cabo durante la conferencia Computer Aided Verification (CAV), ^{[23] [24]} pero a partir de 2020 la competencia se organiza como parte del Taller SMT, que está afiliado a la Conferencia Conjunta Internacional sobre Razonamiento Automatizado (IJCAR). ^[25]

Aplicaciones

Los solucionadores SMT son útiles tanto para la verificación, que prueba la corrección de los programas, como para las pruebas de software basadas en la ejecución simbólica , y para la síntesis , que genera fragmentos de programas mediante la búsqueda en el espacio de programas posibles. Además de la verificación de software, los solucionadores SMT también se han utilizado para la inferencia de tipos ^{[26] [27]} y para modelar escenarios teóricos, incluido el modelado de las creencias de los actores en el control de armas nucleares . ^[28]

Verificación

La verificación asistida por computadora de programas informáticos suele utilizar solucionadores SMT. Una técnica común es traducir las condiciones previas, las condiciones posteriores, las condiciones de bucle y las afirmaciones en fórmulas SMT para determinar si se cumplen todas las propiedades.

Existen muchos verificadores construidos sobre el solucionador SMT Z3 . Boogie es un lenguaje de verificación intermedio que utiliza Z3 para verificar automáticamente programas imperativos simples. El verificador VCC para C concurrente utiliza Boogie, así como Dafny para programas imperativos basados ​​en objetos, Chalice para programas concurrentes y Spec# para C#. F* es un lenguaje de tipado dependiente que utiliza Z3 para encontrar pruebas; el compilador lleva estas pruebas a través de la producción de bytecode que las lleva. La infraestructura de verificación Viper codifica las condiciones de verificación a Z3. La biblioteca sbv proporciona verificación basada en SMT de programas Haskell y permite al usuario elegir entre una serie de solucionadores como Z3, ABC, Boolector, cvc5, MathSAT y Yices.

También hay muchos verificadores creados sobre el solucionador Alt-Ergo SMT. A continuación, se incluye una lista de aplicaciones maduras:

• Why3, una plataforma para la verificación deductiva de programas, utiliza Alt-Ergo como su principal demostrador;
• CAVEAT, un verificador C desarrollado por CEA y utilizado por Airbus; Alt-Ergo fue incluido en la calificación DO-178C de uno de sus aviones recientes;
• Frama-C , un marco para analizar código C, utiliza Alt-Ergo en los complementos Jessie y WP (dedicados a la "verificación deductiva de programas");
• SPARK utiliza CVC4 y Alt-Ergo (detrás de GNATprove) para automatizar la verificación de algunas afirmaciones en SPARK 2014;
• Atelier-B puede utilizar Alt-Ergo en lugar de su probador principal (aumentando el éxito del 84% al 98% en los puntos de referencia del proyecto ANR Bware);
• Rodin , un marco de trabajo del método B desarrollado por Systerel, puede utilizar Alt-Ergo como back-end;
• Cubicle, un verificador de modelos de código abierto para verificar las propiedades de seguridad de los sistemas de transición basados ​​en matrices.
• EasyCrypt, un conjunto de herramientas para razonar sobre las propiedades relacionales de los cálculos probabilísticos con código adversarial.

Muchos solucionadores SMT implementan un formato de interfaz común llamado SMTLIB2 (estos archivos suelen tener la extensión " .smt2"). La herramienta LiquidHaskell implementa un verificador basado en tipos de refinamiento para Haskell que puede utilizar cualquier solucionador compatible con SMTLIB2, por ejemplo, cvc5, MathSat o Z3.

Análisis y pruebas basados ​​en ejecución simbólica

Una aplicación importante de los solucionadores SMT es la ejecución simbólica para el análisis y prueba de programas (por ejemplo, pruebas concólicas ), dirigidas particularmente a encontrar vulnerabilidades de seguridad. ^{[ cita requerida ]} Las herramientas de ejemplo en esta categoría incluyen SAGE de Microsoft Research , KLEE, S2E y Triton. Los solucionadores SMT que se han utilizado para aplicaciones de ejecución simbólica incluyen Z3, STP Archivado el 6 de abril de 2015 en Wayback Machine , la familia de solucionadores Z3str y Boolector. ^{[ cita requerida ]}

Demostración interactiva de teoremas

Los solucionadores SMT se han integrado con asistentes de prueba, incluidos Coq ^[29] e Isabelle/HOL . ^[30]

Véase también

• Programación de conjuntos de respuestas
• Demostración automática de teoremas
• Solucionador SAT
• Lógica de primer orden
• Teoría de la igualdad pura

Notas

1. Blanchette, Jasmin Christian; Böhme, Sascha; Paulson, Lawrence C. (1 de junio de 2013). "Extending Sledgehammer with SMT Solvers". Journal of Automated Reasoning . 51 (1): 109–128. doi :10.1007/s10817-013-9278-5. ISSN  1573-0670. Los ATP y los solucionadores SMT tienen puntos fuertes complementarios. Los primeros manejan los cuantificadores de forma más elegante, mientras que los segundos sobresalen en problemas grandes, principalmente de base.
2. Weber, Tjark; Conchon, Sylvain; Déharbe, David; Heizmann, Matthias; Niemetz, Aina; Reger, Giles (1 de enero de 2019). "La competencia SMT 2015-2018". Revista sobre satisfacibilidad, modelado booleano y computación . 11 (1): 221–259. doi : 10.3233/SAT190123 . S2CID  210147712. En los últimos años, hemos visto una difuminación de las líneas entre SMT-COMP y CASC con los solucionadores SMT compitiendo en CASC y los ATP compitiendo en SMT-COMP.
3. Barbosa, Haniel; Reynolds, Andrew; El Ouraoui, Daniel; Tinelli, Cesare; Barrett, Clark (2019). "Extendiendo los solucionadores SMT a la lógica de orden superior". Deducción automática – CADE 27: 27.ª Conferencia internacional sobre deducción automática, Natal, Brasil, 27-30 de agosto de 2019, Actas . Springer. págs. 35-54. doi :10.1007/978-3-030-29436-6_3. ISBN 978-3-030-29436-6. S2CID  85443815. hal-02300986.
4. Bruttomesso, Roberto; Cimatti, Alessandro; Franzén, Anders; Griggio, Alberto; Hanna, Ziyad; Nadel, Alexander; Palti, Amit; Sebastiani, Roberto (2007). "Un solucionador SMT ($\mathcal{BV}$) perezoso y en capas para problemas de verificación industrial difíciles". En Damm, Werner; Hermanns, Holger (eds.). Verificación asistida por computadora . Apuntes de clase en informática. Vol. 4590. Berlín, Heidelberg: Springer. págs. 547–560. doi :10.1007/978-3-540-73368-3_54. ISBN 978-3-540-73368-3.
5. Nieuwenhuis, R.; Oliveras, A.; Tinelli, C. (2006), "Resolución de teorías SAT y SAT módulo: desde un procedimiento abstracto Davis-Putnam-Logemann-Loveland hasta DPLL(T)" (PDF) , Journal of the ACM , vol. 53, págs. 937–977, doi :10.1145/1217856.1217859, S2CID  14058631
6. de Moura, Leonardo; Bjørner, Nikolaj (12-15 de agosto de 2008). "Decidir eficazmente la lógica proposicional utilizando DPLL y conjuntos de sustitución". En Armando, Alessandro; Baumgartner, Peter; Dowek, Gilles (eds.). Razonamiento automatizado . 4.ª Conferencia conjunta internacional sobre razonamiento automatizado, Sídney, NSW, Australia. Lecture Notes in Computer Science. Berlín, Heidelberg: Springer. págs. 410-425. doi :10.1007/978-3-540-71070-7_35. ISBN 978-3-540-71070-7.
7. Hadarean, Liana; Bansal, Kshitij; Jovanović, Dejan; Barrett, Clark; Tinelli, Cesare (2014). "Una historia de dos solucionadores: enfoques ansiosos y perezosos para los vectores de bits". En Biere, Armin; Bloem, Roderick (eds.). Verificación asistida por computadora . Apuntes de clase en informática. Vol. 8559. Cham: Springer International Publishing. págs. 680–695. doi :10.1007/978-3-319-08867-9_45. ISBN 978-3-319-08867-9.
8. Brain, Martin; Schanda, Florian; Sun, Youcheng (2019). "Building Better Bit-Blasting for Floating-Point Problems". En Vojnar, Tomáš; Zhang, Lijun (eds.). Herramientas y algoritmos para la construcción y análisis de sistemas . 25.ª Conferencia internacional, Herramientas y algoritmos para la construcción y análisis de sistemas 2019, Praga, República Checa, 6-11 de abril de 2019, Actas, Parte I. Notas de clase en informática. Cham: Springer International Publishing. págs. 79-98. doi : 10.1007/978-3-030-17462-0_5 . ISBN 978-3-030-17462-0.S2CID 92999474  .
9. Brain, Martin; Niemetz, Aina; Preiner, Mathias; Reynolds, Andrew; Barrett, Clark; Tinelli, Cesare (2019). "Condiciones de invertibilidad para fórmulas de punto flotante". En Dillig, Isil; Tasiran, Serdar (eds.). Verificación asistida por computadora . 31.ª Conferencia internacional, Verificación asistida por computadora 2019, Nueva York, 15-18 de julio de 2019. Notas de clase en informática. Cham: Springer International Publishing. págs. 116-136. doi : 10.1007/978-3-030-25543-5_8 . ISBN. 978-3-030-25543-5. Número de identificación del sujeto  196613701.
10. Liang, Tianyi; Tsiskaridze, Nestan; Reynolds, Andrew; Tinelli, Cesare; Barrett, Clark (2015). "Un procedimiento de decisión para restricciones de longitud y pertenencia regular sobre cadenas no acotadas". En Lutz, Carsten; Ranise, Silvio (eds.). Fronteras de la combinación de sistemas . Apuntes de clase en informática. Vol. 9322. Cham: Springer International Publishing. págs. 135–150. doi :10.1007/978-3-319-24246-0_9. ISBN 978-3-319-24246-0.
11. Reynolds, Andrew; Blanchette, Jasmin Christian (2015). "Un procedimiento de decisión para (co)tipos de datos en solucionadores SMT". En Felty, Amy P.; Middeldorp, Aart (eds.). Deducción automatizada - CADE-25 . Apuntes de clase en informática. Vol. 9195. Cham: Springer International Publishing. págs. 197–213. doi :10.1007/978-3-319-21401-6_13. ISBN 978-3-319-21401-6.
12. Sheng, Ying; Nötzli, Andres; Reynolds, Andrew; Zohar, Yoni; Dill, David; Grieskamp, ​​Wolfgang; Park, Junkil; Qadeer, Shaz; Barrett, Clark; Tinelli, Cesare (15 de septiembre de 2023). "Razonamiento sobre vectores: satisfacibilidad módulo una teoría de secuencias". Revista de razonamiento automatizado . 67 (3): 32. doi :10.1007/s10817-023-09682-2. ISSN  1573-0670. S2CID  261829653.
13. Bansal, Kshitij; Reynolds, Andrew; Barrett, Clark; Tinelli, Cesare (2016). "Un nuevo procedimiento de decisión para conjuntos finitos y restricciones de cardinalidad en SMT". En Olivetti, Nicola; Tiwari, Ashish (eds.). Razonamiento automatizado . Notas de clase en informática. Vol. 9706. Cham: Springer International Publishing. págs. 82–98. doi :10.1007/978-3-319-40229-1_7. ISBN 978-3-319-40229-1.
14. Meng, Baoluo; Reynolds, Andrew; Tinelli, Cesare; Barrett, Clark (2017). "Resolución de restricciones relacionales en SMT". En de Moura, Leonardo (ed.). Deducción automatizada – CADE 26. Apuntes de clase en informática. Vol. 10395. Cham: Springer International Publishing. págs. 148–165. doi :10.1007/978-3-319-63046-5_10. ISBN 978-3-319-63046-5.
15. Reynolds, Andrew; Iosif, Radu; Serban, Cristina; King, Tim (2016). "Un procedimiento de decisión para la lógica de separación en SMT" (PDF) . En Artho, Cyrille; Legay, Axel; Peled, Doron (eds.). Tecnología automatizada para verificación y análisis . Apuntes de clase en informática. Vol. 9938. Cham: Springer International Publishing. págs. 244–261. doi :10.1007/978-3-319-46520-3_16. ISBN 978-3-319-46520-3. Número de identificación del sujeto  6753369.
16. Ozdemir, Alex; Kremer, Gereon; Tinelli, Cesare; Barrett, Clark (2023). "Satisfacción módulo campos finitos". En Enea, Constantin; Lal, Akash (eds.). Verificación asistida por computadora . Apuntes de clase en informática. Vol. 13965. Cham: Springer Nature Switzerland. págs. 163–186. doi :10.1007/978-3-031-37703-7_8. ISBN 978-3-031-37703-7.S2CID257235627  .​
17. Bayless, Sam; Bayless, Noah; Hoos, Holger; Hu, Alan (4 de marzo de 2015). "Teorías monotónicas del módulo SAT". Actas de la Conferencia AAAI sobre Inteligencia Artificial . 29 (1). arXiv : 1406.0043 . doi : 10.1609/aaai.v29i1.9755 . ISSN  2374-3468. S2CID  9567647.
18. Klenze, Tobías; Sin bahía, Sam; Hu, Alan J. (2016). "Síntesis de CTL rápida, flexible y mínima mediante SMT". En Chaudhuri, Swarat; Farzan, Azadeh (eds.). Verificación asistida por computadora . Apuntes de conferencias sobre informática. vol. 9779. Cham: Editorial Internacional Springer. págs. 136-156. doi :10.1007/978-3-319-41528-4_8. ISBN 978-3-319-41528-4.
19. Bembenek, Aaron; Greenberg, Michael; Chong, Stephen (11 de enero de 2023). "De SMT a ASP: enfoques basados ​​en solucionadores para resolver problemas de síntesis de registros de datos como selección de reglas". Actas de la ACM sobre lenguajes de programación . 7 (POPL): 7:185–7:217. doi : 10.1145/3571200 . S2CID  253525805.
20. Bauer, A.; Pister, M.; Tautschnig, M. (2007), "Herramientas de apoyo para el análisis de sistemas y modelos híbridos", Actas de la Conferencia de 2007 sobre diseño, automatización y pruebas en Europa (DATE'07) , IEEE Computer Society, pág. 1, CiteSeerX 10.1.1.323.6807 , doi :10.1109/DATE.2007.364411, ISBN  978-3-9810801-2-4, Número de identificación del sujeto  9159847
21. Fränzle, M.; Herde, C.; Ratschan, S.; Schubert, T.; Teige, T. (2007), "Resolución eficiente de grandes sistemas de restricciones aritméticas no lineales con estructura booleana compleja" (PDF) , Journal on Satisfiability, Boolean Modeling and Computation , 1 (número especial de JSAT 3-4 sobre integración SAT/CP): 209-236, doi :10.3233/SAT190012
22. Barbosa, Haniel; Barrett, Clark; Brain, Martin; Kremer, Gereon; Lachnitt, Hanna; Mann, Makai; Mohamed, Abdalrhman; Mohamed, Mudathir; Niemetz, Aina; Nötzli, Andres; Ozdemir, Alex; Preiner, Mathias; Reynolds, Andrew; Sheng, Ying; Tinelli, Cesare (2022). "cvc5: Un solucionador SMT versátil y de potencia industrial". En Fisman, Dana; Rosu, Grigore (eds.). Herramientas y algoritmos para la construcción y análisis de sistemas, 28.ª Conferencia Internacional . Apuntes de clase en informática. Vol. 13243. Cham: Springer International Publishing. págs. 415–442. doi :10.1007/978-3-030-99524-9_24. ISBN 978-3-030-99524-9.S2CID247857361  .​
23. Barrett, Clark; de Moura, Leonardo; Stump, Aaron (2005). "SMT-COMP: Competencia de teorías de satisfacibilidad módulo". En Etessami, Kousha; Rajamani, Sriram K. (eds.). Verificación asistida por computadora . Apuntes de clase en informática. Vol. 3576. Springer. págs. 20–23. doi :10.1007/11513988_4. ISBN . 978-3-540-31686-2.
24. Barrett, Clark; de Moura, Leonardo; Ranise, Silvio; Stump, Aaron; Tinelli, Cesare (2011). "La iniciativa SMT-LIB y el auge de SMT: (Charla del premio HVC 2010)". En Barner, Sharon; Harris, Ian; Kroening, Daniel; Raz, Orna (eds.). Hardware y software: verificación y pruebas . Notas de clase en informática. Vol. 6504. Springer. p. 3. Bibcode :2011LNCS.6504....3B. doi : 10.1007/978-3-642-19583-9_2 . ISBN 978-3-642-19583-9.
25. "SMT-COMP 2020". SMT-COMP . Consultado el 19 de octubre de 2020 .
26. Hassan, Mostafa; Urban, Caterina; Eilers, Marco; Müller, Peter (2018). "Inferencia de tipos basada en MaxSMT para Python 3". Verificación asistida por computadora . Apuntes de clase en informática. Vol. 10982. págs. 12–19. doi :10.1007/978-3-319-96142-2_2. ISBN 978-3-319-96141-5.
27. Loncaric, Calvin, et al. "Un marco práctico para la explicación de errores de inferencia de tipos". ACM SIGPLAN Notices 51.10 (2016): 781-799.
28. Beaumont, Paul; Evans, Neil; Huth, Michael; Plant, Tom (2015). "Análisis de confianza para el control de armas nucleares: abstracciones SMT de redes de creencias bayesianas". En Pernul, Günther; YA Ryan, Peter; Weippl, Edgar (eds.). Seguridad informática -- ESORICS 2015 . Apuntes de clase en informática. Vol. 9326. Springer. págs. 521–540. doi : 10.1007/978-3-319-24174-6_27 . ISBN 978-3-319-24174-6.
29. Ekici, Burak; Mebsout, Alain; Tinelli, Cesare; Keller, Chantal; Katz, Guy; Reynolds, Andrew; Barrett, Clark (2017). "SMTCoq: un complemento para integrar solucionadores SMT en Coq" (PDF) . En Majumdar, Rupak; Kunčak, Viktor (eds.). Verificación asistida por computadora, 29.ª Conferencia Internacional . Apuntes de clase en informática. Vol. 10427. Cham: Springer International Publishing. págs. 126–133. doi :10.1007/978-3-319-63390-9_7. ISBN 978-3-319-63390-9.S2CID206701576  .​
30. Blanchette, Jasmin Christian; Böhme, Sascha; Paulson, Lawrence C. (1 de junio de 2013). "Extensión de Sledgehammer con solucionadores SMT". Revista de razonamiento automatizado . 51 (1): 109–128. doi :10.1007/s10817-013-9278-5. ISSN  1573-0670.

Referencias

• Barrett, C.; Sebastiani, R.; Seshia, S.; Tinelli, C. (2009). "Teorías del módulo de satisfacibilidad". En Biere, A.; Heule, MJH; van Maaren, H.; Walsh, T. (eds.). Manual de satisfacibilidad . Fronteras en inteligencia artificial y aplicaciones. Vol. 185. IOS Press. págs. 825–885. ISBN 9781607503767.
• Ganesh, Vijay (septiembre de 2007). Procedimientos de decisión para vectores de bits, matrices y números enteros (PDF) (PhD). Departamento de Ciencias de la Computación, Universidad de Stanford.
• Jha, Susmit; Limaye, Rhishikesh; Seshia, Sanjit A. (2009). "Beaver: Ingeniería de un solucionador SMT eficiente para aritmética de vectores de bits". Actas de la 21.ª Conferencia internacional sobre verificación asistida por ordenador . págs. 668–674. doi :10.1007/978-3-642-02658-4_53. ISBN . 978-3-642-02658-4.
• Bryant, RE; German, SM; Velev, MN (1999). "Verificación de microprocesadores mediante procedimientos de decisión eficientes para una lógica de igualdad con funciones no interpretadas" (PDF) . Tablas analíticas y métodos relacionados . págs. 1–13., págs., .
• Davis, M.; Putnam, H. (1960). "Un procedimiento computacional para la teoría de cuantificación". Revista de la Asociación de Maquinaria Computacional . 7 (3): 201–215. doi : 10.1145/321033.321034 . S2CID  31888376.
• Davis, M.; Logemann, G.; Loveland, D. (1962). "Un programa de máquina para la demostración de teoremas". Comunicaciones de la ACM . 5 (7): 394–397. doi :10.1145/368273.368557. hdl : 2027/mdp.39015095248095 . S2CID  15866917.
• Kroening, D.; Strichman, O. (2008). Procedimientos de decisión: un punto de vista algorítmico. Serie de Ciencias de la Computación Teórica. Springer. ISBN 978-3-540-74104-6.
• Nam, G.-J.; Sakallah, KA; Rutenbar, R. (2002). "Un nuevo enfoque de enrutamiento detallado de FPGA mediante satisfacibilidad booleana basada en búsqueda". Transacciones IEEE sobre diseño asistido por computadora de circuitos y sistemas integrados . 21 (6): 674–684. doi :10.1109/TCAD.2002.1004311.
• SMT-LIB: La biblioteca de teorías del módulo de satisfacibilidad
• SMT-COMP: La competencia de teorías del módulo de satisfacibilidad
• Procedimientos de decisión: un punto de vista algorítmico
• Sebastiani, R. (2007). "Teorías del módulo de satisfacibilidad perezosa". Revista sobre satisfacibilidad, modelado booleano y computación . 3 (3–4): 141–224. CiteSeerX  10.1.1.100.221 . doi :10.3233/SAT190034.

Este artículo fue adaptado originalmente de una columna del boletín electrónico SIGDA de la ACM escrita por el profesor Karem A. Sakallah . El texto original está disponible aquí