Teorías del módulo de satisfacción

Problema lógico estudiado en informática.

En informática y lógica matemática , las teorías del módulo de satisfacibilidad ( SMT ) son el problema de determinar si una fórmula matemática es satisfactible . Generaliza el problema de satisfacibilidad booleana (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 ("módulo") de una determinada teoría formal en lógica de primer orden con igualdad (a menudo no permite 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 componente básico 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 suele ser NP-difícil 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 solucionadores SMT; véase, por ejemplo, la decidibilidad de la aritmética de Presburger . Se puede pensar en SMT como un problema de satisfacción de restricciones y, por lo tanto, como un cierto enfoque formalizado para la programación de restricciones .

Terminología y ejemplos

Hablando formalmente, una instancia de SMT es una fórmula en lógica de primer orden , donde algunas funciones y símbolos de predicados tienen interpretaciones adicionales, y SMT es el problema de determinar si dicha fórmula es satisfactoria. En otras palabras, imagine un caso del problema booleano de satisfacibilidad (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 con valores binarios 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 funciones (p. ej., donde hay alguna función no especificada de dos argumentos). Estos predicados se clasifican según 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 funciones 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 de diferencias es una subteoría de la aritmética lineal en la que cada desigualdad está restringida a tener la forma de variables yy constante . ${\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 enteros sobre desigualdades. Otros ejemplos incluyen:

• Satisfacibilidad: Determinar si es satisfactoria. ${\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: determine si xey son números distintos de 3 bits.
• Funciones no interpretadas: encuentre valores para xey 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 libres de cuantificadores . ^{[ cita necesaria ]}

Relación con la demostración automatizada de teoremas

Existe una superposición sustancial entre la resolución SMT y la demostración automatizada de teoremas . Generalmente, los demostradores de teoremas automatizados se centran en respaldar la lógica completa de primer orden con cuantificadores, mientras que los solucionadores de SMT se centran más en respaldar varias teorías (símbolos de predicados interpretados). Los ATP sobresalen 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 de SMT participan en CASC . ^[2]

poder expresivo

Una instancia SMT es una generalización de una instancia booleana SAT en la que varios conjuntos de variables se reemplazan 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 booleanas SAT. 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 bits.

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 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 de diferencias; la programación de conjuntos de respuestas se adapta mejor a problemas booleanos que se reducen a la teoría libre de funciones no interpretadas. La implementación de 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: 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 necesaria ]} 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 SMT involucraron traducirlas a instancias SAT booleanas (por ejemplo, una variable entera de 32 bits sería codificada por 32 variables de un solo bit con pesos apropiados y operaciones a nivel de palabra como 'más' serían reemplazadas por variables de nivel inferior). operaciones lógicas de nivel en los bits) y pasar esta fórmula a un solucionador SAT booleano. Este enfoque, que se conoce como enfoque ansioso (o bitblasting ), tiene sus ventajas: al preprocesar la fórmula SMT en una fórmula booleana SAT equivalente, los solucionadores booleanos SAT existentes se pueden utilizar "tal cual" y su rendimiento y capacidad . mejoras aprovechadas a lo largo del tiempo. Por otro lado, la pérdida de la semántica de alto nivel de las teorías subyacentes significa que el solucionador booleano SAT tiene que trabajar mucho más de lo necesario para descubrir hechos "obvios" (como la suma de números enteros). 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 teoría ( T-solvers ) que manejan conjunciones (AND) de predicados de una teoría determinada. Este enfoque se conoce como 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 para la teoría T a través de una interfaz bien definida. El solucionador de teorías sólo necesita preocuparse por comprobar la viabilidad de las conjunciones de predicados teóricos 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, quien resuelve la teoría debe poder participar en la propagación y el análisis de conflictos, es decir, debe poder inferir nuevos hechos a partir de hechos ya establecidos, así como proporcionar explicaciones sucintas de la inviabilidad cuando la teoría entra en conflicto. surgir. En otras palabras, el solucionador de teorías debe ser incremental y retrospectivo .

Teorías decidibles

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. Dado que la lógica de primer orden completa es sólo 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 , incluida la 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 mediante explosión de bits , es decir, reducción a vectores de bits), ^{[8] [9]} cadenas , ^[10] (co)-tipos de datos , ^[11] secuencias (utilizadas para modelar matrices dinámicas ), ^[12] conjuntos finitos y relaciones , ^{[13] [14]} lógica de separación , ^[15] finitos campos , ^[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 su uso práctico dentro de los solucionadores DPLL(T). ^[17] Las teorías monótonas solo admiten variables booleanas (la booleana 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 )}$

Ejemplos de teorías monótonas incluyen la accesibilidad de gráficos , la detección de colisiones para cascos convexos , los cortes mínimos y la lógica de á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 respaldan teorías decidibles . Sin embargo, muchos sistemas del mundo real, como un avión y su comportamiento, sólo pueden modelarse mediante aritmética no lineal sobre 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 satisfactoria:

${\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, en general estos problemas son insolubles . (Por otro lado, la teoría de campos cerrados reales y, por tanto, la teoría completa de primer orden de los números reales , se pueden decidir mediante la eliminación de cuantificadores . Esto se debe a Alfred Tarski ). La teoría de primer orden de los números naturales con suma ( pero no la multiplicación), llamada aritmética de Presburger , también es decidible. Dado que la multiplicación por constantes se puede implementar como sumas anidadas, la aritmética en muchos programas de computadora se puede expresar usando la aritmética de Presburger, lo que da como resultado fórmulas decidibles.

Ejemplos de solucionadores SMT que abordan combinaciones booleanas de átomos teóricos de teorías aritméticas indecidibles sobre los reales son ABsolver, ^[20] que emplea una arquitectura DPLL(T) clásica con un paquete de optimización no lineal como solucionador teórico subordinado (necesariamente incompleto), iSAT, basándose en una unificación de la resolución DPLL SAT 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 muchos solucionadores SMT disponibles. La columna "SMT-LIB" indica compatibilidad con el lenguaje SMT-LIB; Es posible que muchos sistemas marcados con "sí" solo admitan versiones anteriores de SMT-LIB u ofrezcan solo soporte parcial para el idioma. La columna "CVC" indica compatibilidad con el lenguaje CVC . La columna "DIMACS" indica compatibilidad con el formato DIMACS .

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

Estandarización y competencia de solucionadores SMT-COMP

Existen múltiples intentos de describir una interfaz estandarizada para los solucionadores SMT (y demostradores de teoremas automatizados , un término que a menudo se usa como sinónimo). El más destacado es el estándar SMT-LIB, ^{[ cita necesaria ]} que proporciona un lenguaje basado en expresiones S. Otros formatos estandarizados comúnmente admitidos son el formato DIMACS ^{[ cita necesaria ]} respaldado por muchos solucionadores booleanos SAT y el formato CVC ^{[ cita necesaria ]} utilizado por el probador de teoremas automatizado 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 de Verificación Asistida por Computadora (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, demostrando la corrección de los programas, pruebas de software basadas en ejecución simbólica , como para la síntesis , generando fragmentos de programas buscando en el espacio de posibles programas. 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 a menudo utiliza solucionadores SMT. Una técnica común es traducir condiciones previas, condiciones posteriores, condiciones de bucle y aserciones en fórmulas SMT para determinar si todas las propiedades pueden cumplirse.

Hay muchos verificadores integrados 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 de 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 escrito de forma dependiente que utiliza Z3 para encontrar pruebas; el compilador lleva estas pruebas para producir un código de bytes que porta pruebas. La infraestructura de verificación de Viper codifica las condiciones de verificación en Z3. La biblioteca sbv proporciona verificación basada en SMT de programas Haskell y permite al usuario elegir entre varios solucionadores como Z3, ABC, Boolector, cvc5, MathSAT y Yices.

También hay muchos verificadores integrados sobre el solucionador Alt-Ergo SMT. Aquí hay una lista de aplicaciones maduras:

• Why3, una plataforma para la verificación deductiva de programas, utiliza Alt-Ergo como probador principal;
• 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 usa 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 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 sistemas de transición basados ​​en matrices.
• EasyCrypt, un conjunto de herramientas para razonar sobre propiedades relacionales de cálculos probabilísticos con código adversario.

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 usar 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 ), destinadas particularmente a encontrar vulnerabilidades de seguridad. ^{[ cita necesaria ]} 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 necesaria ]}

Demostración interactiva de teoremas

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

Ver también

• Programación del conjunto de respuestas
• Demostración automatizada de teoremas
• solucionador SAT
• Lógica de primer orden
• Teoría de la igualdad pura

Notas

1. Blanchette, Jasmín Christian; Böhme, Sascha; Paulson, Lawrence C. (1 de junio de 2013). "Mazo extensible con solucionadores SMT". Revista de razonamiento automatizado . 51 (1): 109-128. doi :10.1007/s10817-013-9278-5. ISSN  1573-0670. Los solucionadores de ATP y SMT tienen fortalezas complementarias. Los primeros manejan los cuantificadores con mayor elegancia, mientras que los segundos destacan en problemas grandes, en su mayoría básicos.
2. Weber, Tjark; Conchón, Sylvain; Déharbe, David; Heizmann, Matías; Niemetz, Aina; Reger, Giles (1 de enero de 2019). "El concurso 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 línea borrosa entre SMT-COMP y CASC con solucionadores de SMT compitiendo en CASC y ATP compitiendo en SMT-COMP.
3. Barbosa, Haniel; Reynolds, Andrés; El Ouraoui, Daniel; Tinelli, César; Barrett, Clark (2019). "Ampliación de los solucionadores SMT a la lógica de orden superior". Deducción automatizada – CADE 27: 27.° Congreso Internacional sobre Deducción Automatizada, Natal, Brasil, 27 al 30 de agosto de 2019, Actas . Saltador. 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; Franzen, Anders; Grigio, Alberto; Hanna, Ziyad; Nadel, Alejandro; Palti, Amit; Sebastiani, Roberto (2007). "Un solucionador SMT( $\mathcal{BV}$ ) perezoso y en capas para problemas difíciles de verificación industrial". En Damm, Werner; Hermanns, Holger (eds.). Verificación asistida por computadora . Apuntes de conferencias sobre 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 de módulo SAT y SAT: de un procedimiento abstracto de Davis-Putnam-Logemann-Loveland a 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 al 15 de agosto de 2008). "Decidir eficazmente la lógica proposicional utilizando DPLL y conjuntos de sustitución". En Armando, Alejandro; Baumgartner, Peter; Dowek, Gilles (eds.). Razonamiento automatizado . Cuarta Conferencia Internacional Conjunta sobre Razonamiento Automatizado, Sydney, NSW, Australia. Apuntes de conferencias sobre informática. 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, César (2014). "Una historia de dos solucionadores: enfoques entusiastas y perezosos de los vectores de bits". En Biere, Armin; Bloem, Roderick (eds.). Verificación asistida por computadora . Apuntes de conferencias sobre informática. vol. 8559. Cham: Editorial Internacional Springer. págs. 680–695. doi :10.1007/978-3-319-08867-9_45. ISBN 978-3-319-08867-9.
8. Cerebro, Martín; Schanda, Florián; Sol, Youcheng (2019). "Construcción de una mejor explosión de bits para problemas de punto flotante". En Vojnar, Tomaš; 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 al 11 de abril de 2019, Actas, Parte I. Apuntes de conferencias sobre informática. Cham: Editorial Internacional Springer. págs. 79–98. doi : 10.1007/978-3-030-17462-0_5 . ISBN 978-3-030-17462-0. S2CID  92999474.
9. Cerebro, Martín; Niemetz, Aina; Preiner, Mathías; Reynolds, Andrés; Barrett, Clark; Tinelli, César (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, ciudad de Nueva York, 15 al 18 de julio de 2019. Apuntes de conferencias sobre informática. Cham: Editorial Internacional Springer. págs. 116-136. doi : 10.1007/978-3-030-25543-5_8 . ISBN 978-3-030-25543-5. S2CID  196613701.
10. Liang, Tianyi; Tsiskaridze, Nestan; Reynolds, Andrés; Tinelli, César; Barrett, Clark (2015). "Un procedimiento de decisión para membresía regular y restricciones de longitud sobre cadenas ilimitadas". En Lutz, Carsten; Ranise, Silvio (eds.). Fronteras de la combinación de sistemas . Apuntes de conferencias sobre informática. vol. 9322. Cham: Editorial Internacional Springer. págs. 135-150. doi :10.1007/978-3-319-24246-0_9. ISBN 978-3-319-24246-0.
11. Reynolds, Andrés; Blanchette, Jasmin Christian (2015). "Un procedimiento de decisión para (Co) tipos de datos en SMT Solvers". En Felty, Amy P.; Middeldorp, Aart (eds.). Deducción Automatizada - CADE-25 . Apuntes de conferencias sobre informática. vol. 9195. Cham: Editorial Internacional Springer. págs. 197-213. doi :10.1007/978-3-319-21401-6_13. ISBN 978-3-319-21401-6.
12. Sheng, Ying; Nötzli, Andrés; Reynolds, Andrés; Zohar, Yoni; Eneldo, David; Grieskamp, ​​Wolfgang; Parque, Junkil; Qadeer, Shaz; Barrett, Clark; Tinelli, César (15 de septiembre de 2023). "Razonamiento sobre vectores: módulo de satisfacción, 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, Andrés; Barrett, Clark; Tinelli, César (2016). "Un nuevo procedimiento de decisión para conjuntos finitos y restricciones de cardinalidad en SMT". En Olivetti, Nicola; Tiwari, Ashish (eds.). Razonamiento automatizado . Apuntes de conferencias sobre informática. vol. 9706. Cham: Editorial Internacional Springer. págs. 82–98. doi :10.1007/978-3-319-40229-1_7. ISBN 978-3-319-40229-1.
14. Meng, Baoluo; Reynolds, Andrés; Tinelli, César; Barrett, Clark (2017). "Resolución de restricciones relacionales en SMT". En de Moura, Leonardo (ed.). Deducción Automatizada – CADE 26 . Apuntes de conferencias sobre informática. vol. 10395. Cham: Editorial Internacional Springer. págs. 148-165. doi :10.1007/978-3-319-63046-5_10. ISBN 978-3-319-63046-5.
15. Reynolds, Andrés; José, Radu; Serban, Cristina; Rey, 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 conferencias sobre informática. vol. 9938. Cham: Editorial Internacional Springer. págs. 244–261. doi :10.1007/978-3-319-46520-3_16. ISBN 978-3-319-46520-3. S2CID  6753369.
16. Ozdemir, Alex; Kremer, Gereon; Tinelli, César; Barrett, Clark (2023). "Módulo de satisfacción de campos finitos". En Enea, Constantino; Lal, Akash (eds.). Verificación asistida por computadora . Apuntes de conferencias sobre informática. vol. 13965. Cham: Springer Nature Suiza. págs. 163–186. doi :10.1007/978-3-031-37703-7_8. ISBN 978-3-031-37703-7. S2CID  257235627.
17. Sin bahía, Sam; Bayless, Noé; Hoos, Holger; Hu, Alan (4 de marzo de 2015). "Teorías del módulo monótono del 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, Aarón; Greenberg, Michael; Chong, Stephen (11 de enero de 2023). "De SMT a ASP: enfoques basados ​​en Solver 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), "Herramienta de soporte 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 (FECHA'07) , IEEE Computer Society, p. 1, CiteSeerX 10.1.1.323.6807 , doi :10.1109/FECHA.2007.364411, ISBN  978-3-9810801-2-4, S2CID  9159847
21. Franzle, 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) , Revista sobre satisfacción, modelado booleano y computación , 1 (3–4 Número especial de JSAT sobre integración SAT/CP ): 209–236, doi :10.3233/SAT190012
22. Barbosa, Haniel; Barrett, Clark; Cerebro, Martín; Kremer, Gereon; Lachnitt, Hanna; Mann, Makai; Mohamed, Abdalrhman; Mohamed, Mudathir; Niemetz, Aina; Nötzli, Andrés; Özdemir, Alex; Preiner, Mathías; Reynolds, Andrés; Sheng, Ying; Tinelli, César (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° Congreso Internacional . Apuntes de conferencias sobre 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. S2CID  247857361.
23. Barrett, Clark; de Moura, Leonardo; Tocón, Aaron (2005). "SMT-COMP: Concurso de teorías del módulo de satisfacción". En Etessami, Kousha; Rajamani, Sriram K. (eds.). Verificación asistida por computadora . Apuntes de conferencias sobre informática. vol. 3576. Saltador. págs. 20-23. doi :10.1007/11513988_4. ISBN 978-3-540-31686-2.
24. Barrett, Clark; de Moura, Leonardo; Ranise, Silvio; Tocón, Aarón; Tinelli, César (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 . Apuntes de conferencias sobre informática. vol. 6504. Saltador. pag. 3. Código Bib : 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; Urbano, Caterina; Eilers, Marco; Müller, Peter (2018). "Inferencia de tipos basada en MaxSMT para Python 3". Verificación asistida por computadora . Apuntes de conferencias sobre 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 y col. "Un marco práctico para la explicación del error de inferencia de tipos". Avisos ACM SIGPLAN 51.10 (2016): 781-799.
28. Beaumont, Pablo; Evans, Neil; Huth, Michael; Planta, 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 conferencias sobre informática. vol. 9326. Saltador. 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, César; Keller, Chantal; Katz, chico; Reynolds, Andrés; 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 conferencias sobre informática. vol. 10427. Cham: Editorial Internacional Springer. págs. 126-133. doi :10.1007/978-3-319-63390-9_7. ISBN 978-3-319-63390-9. S2CID  206701576.
30. Blanchette, Jasmín Christian; Böhme, Sascha; Paulson, Lawrence C. (1 de junio de 2013). "Mazo extensible 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 satisfacción". En Biere, A.; Heule, MJH; van Maaren, H.; Walsh, T. (eds.). Manual de Satisfacibilidad . Fronteras en Inteligencia Artificial y Aplicaciones. vol. 185. Prensa IOS. págs. 825–885. ISBN 9781607503767.
• Ganesh, Vijay (septiembre de 2007). Procedimientos de decisión para vectores de bits, matrices y enteros (PDF) (Doctor). Departamento de Ciencias de la Computación, Universidad de Stanford.
• Jha, admitir; Limaye, Rhishikesh; Seshia, Sanjit A. (2009). "Beaver: ingeniería de un solucionador SMT eficiente para aritmética de vectores de bits". Actas de la XXI Conferencia Internacional sobre Verificación Asistida por Computadora . págs. 668–674. doi :10.1007/978-3-642-02658-4_53. ISBN 978-3-642-02658-4.
• Bryant, RE; alemán, SM; Velev, MN (1999). "Verificación por microprocesador mediante procedimientos de decisión eficientes para una lógica de igualdad con funciones no interpretadas" (PDF) . Cuadros analíticos y métodos relacionados . págs. 1-13., págs. , .
• Davis, M.; Putnam, H. (1960). "Un procedimiento de cálculo para la teoría de la cuantificación". Revista de la Asociación de Maquinaria de Computación . 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 Teórica de Informática. Saltador. ISBN 978-3-540-74104-6.
• Nam, G.-J.; Sakallah, KA; Rutanbar, R. (2002). "Un nuevo enfoque de enrutamiento detallado de FPGA mediante satisfacibilidad booleana basada en búsquedas". 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: Biblioteca de teorías del módulo de satisfacción
• SMT-COMP: El concurso de teorías del módulo de satisfacción
• Procedimientos de decisión: un punto de vista algorítmico
• Sebastiani, R. (2007). "Teorías del módulo de satisfacción 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 ACM SIGDA del Prof. Karem A. Sakallah . El texto original está disponible aquí.