Satisfiability modulo theories
In computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involving real numbers, integers, and/or various data structures such as lists, arrays, bit vectors, and strings. The name is derived from the fact that these expressions are interpreted within ("modulo") a certain formal theory in first-order logic with equality (often disallowing quantifiers). SMT solvers are tools which aim to solve the SMT problem for a practical subset of inputs. SMT solvers such as Z3 and cvc5 have been used as a building block for a wide range of applications across computer science, including in automated theorem proving, program
- Comment
- enIn computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involving real numbers, integers, and/or various data structures such as lists, arrays, bit vectors, and strings. The name is derived from the fact that these expressions are interpreted within ("modulo") a certain formal theory in first-order logic with equality (often disallowing quantifiers). SMT solvers are tools which aim to solve the SMT problem for a practical subset of inputs. SMT solvers such as Z3 and cvc5 have been used as a building block for a wide range of applications across computer science, including in automated theorem proving, program
- Date
- 6 April 2015
- Has abstract
- enIn computer science and mathematical logic, satisfiability modulo theories (SMT) is the problem of determining whether a mathematical formula is satisfiable. It generalizes the Boolean satisfiability problem (SAT) to more complex formulas involving real numbers, integers, and/or various data structures such as lists, arrays, bit vectors, and strings. The name is derived from the fact that these expressions are interpreted within ("modulo") a certain formal theory in first-order logic with equality (often disallowing quantifiers). SMT solvers are tools which aim to solve the SMT problem for a practical subset of inputs. SMT solvers such as Z3 and cvc5 have been used as a building block for a wide range of applications across computer science, including in automated theorem proving, program analysis, program verification, and software testing. Since Boolean satisfiability is already NP-complete, the SMT problem is typically NP-hard, and for many theories it is undecidable. Researchers study which theories or subsets of theories lead to a decidable SMT problem and the computational complexity of decidable cases. The resulting decision procedures are often implemented directly in SMT solvers; see, for instance, the decidability of Presburger arithmetic. SMT can be thought of as a constraint satisfaction problem and thus a certain formalized approach to constraint programming.
- Hypernym
- Problem
- Is primary topic of
- Satisfiability modulo theories
- Label
- enSatisfiability modulo theories
- Link from a Wikipage to an external page
- www.eecs.umich.edu/~karem
- archive.sigda.org/newsletter/2006/061215.txt
- kilthub.cmu.edu/articles/Microprocessor_Verification_Using_Efficient_Decision_Procedures_for_a_Logic_of_Equality_with_Uninterpreted_Functions/6607286/files/12097826.pdf
- alt-ergo.lri.fr/documents/ABZ-2014.pdf
- books.google.com/books%3Fid=anJsH3Dq5BIC&q=SMT
- books.google.com/books%3Fid=shLvAgAAQBAJ&q=%22Satisfiability+Modulo+Theories%22
- www.satcompetition.org/2009/format-benchmarks2009.html
- alt-ergo.ocamlpro.com/
- cubicle.lri.fr/
- fmv.jku.at/boolector/
- isat.gforge.avacs.org/
- research.microsoft.com/en-us/projects/boogie/
- research.microsoft.com/en-us/projects/chalice/
- research.microsoft.com/en-us/projects/dafny/
- research.microsoft.com/en-us/projects/fstar/
- research.microsoft.com/en-us/projects/specsharp/
- s2e.epfl.ch/
- smtlib.org/
- smt-lib.org/
- why3.lri.fr/
- www.smtcomp.org/
- klee.github.io/
- sites.google.com/site/stpfastprover/
- ucsd-progsys.github.io/liquidhaskell-blog/
- web.archive.org/web/20150406115407/https:/sites.google.com/site/stpfastprover/
- www.easycrypt.info/
- z3string.github.io/
- web.archive.org/web/20070208034716/http:/www.sigda.org/newsletter/index.html
- research.microsoft.com/en-us/um/people/pg/public_psfiles/ndss2008.pdf
- yurichev.com/writings/SAT_SMT_draft-EN.pdf
- hackage.haskell.org/package/sbv
- triton.quarkslab.com
- vcc.codeplex.com
- ece.uwaterloo.ca/~vganesh/Publications_files/vg2007-PhD-STANFORD.pdf
- viper.ethz.ch
- www.sigda.org
- www.smtcomp.org
- github.com/Z3Prover/z3
- Link from a Wikipage to another Wikipage
- .NET Framework
- AC symbol
- Affero General Public License
- Alfred Tarski
- Alt-Ergo
- Answer set programming
- Apache license
- Arithmetic
- Arms control
- Array data structure
- Atomic formula
- Atomic sentence
- Automated theorem proving
- Backtracking
- Binary data
- Bitvector
- Bit vector
- Bit vectors
- B-Method
- Boolean satisfiability problem
- BSD licenses
- C (programming language)
- C++
- Category:Constraint programming
- Category:Electronic design automation
- Category:Formal methods
- Category:Logic in computer science
- Category:NP-complete problems
- Category:Satisfiability problems
- Category:SMT solvers
- CeCILL-C
- Common Public License
- Computational complexity
- Computer Aided Verification
- Computer program
- Computer science
- Concolic testing
- Congruence closure
- Constraint Handling Rules
- Constraint logic programming
- Constraint programming
- Constraint satisfaction problem
- Correctness (computer science)
- Datapath
- Data structure
- Decidability (logic)
- Decision problem
- Difference logic
- DIMACS
- DPLL(T)
- DPLL algorithm
- Eager evaluation
- Empty theory
- Enumerated datatype
- First-order logic
- Formal verification
- Frama-C
- FreeBSD
- Free theory
- GPLv3
- Hardware design
- Haskell (programming language)
- Higher-order logic
- Inequality (mathematics)
- Integers
- International Joint Conference on Automated Reasoning
- Interval arithmetic
- Java (programming language)
- Lazy evaluation
- LGPL
- LGPLv3
- Linear arithmetic
- Linux
- List (computing)
- Logical conjunction
- Mac OS
- Mathematical logic
- Microprocessor
- Microsoft Research
- Microsoft Windows
- MIT License
- Modeling language
- Natural numbers
- NP-hardness
- OCaml
- OpenBSD
- OpenCog
- OS X
- Polymorphic array
- Predicate (mathematical logic)
- Presburger arithmetic
- Probabilistic logic
- Program analysis
- Program synthesis
- Python (programming language)
- Quantifier (logic)
- Quantifier elimination
- Real closed field
- Real number
- Real numbers
- Record datatype
- Relational model
- Rodin tool
- Satisfiability
- Scheme (programming language)
- S-expression
- SPARK (programming language)
- String (computer science)
- Symbolic execution
- Theory (mathematical logic)
- Theory of pure equality
- Transcendental function
- Type inference
- Undecidable problem
- Uninterpreted function
- Uninterpreted term
- Well-formed formula
- White-box testing
- Windows
- Z3 Theorem Prover
- SameAs
- Kielégíthetőségi modulo elméletek
- m.0d4jbt
- Q2067766
- Satisfiability modulo theories
- Satisfiability modulo theories
- Satisfiability Modulo Theories
- Satisfierbarhet modulo teorier
- Teorías de satisfacibilidad módulo
- y5Cm
- Задача выполнимости формул в теориях
- Բանաձևերի լուծելիություն տեսություններում
- صدقپذیری در پیمانه نظریات
- Subject
- Category:Constraint programming
- Category:Electronic design automation
- Category:Formal methods
- Category:Logic in computer science
- Category:NP-complete problems
- Category:Satisfiability problems
- Category:SMT solvers
- Url
- https://web.archive.org/web/20150406115407/https:/sites.google.com/site/stpfastprover/
- WasDerivedFrom
- Satisfiability modulo theories?oldid=1120037167&ns=0
- WikiPageLength
- 31615
- Wikipage page ID
- 5138563
- Wikipage revision ID
- 1120037167
- WikiPageUsesTemplate
- Template:Abbr
- Template:Anchor
- Template:Citation needed
- Template:Cite book
- Template:Cite journal
- Template:Cite thesis
- Template:Cite web
- Template:Mathematical logic
- Template:No
- Template:Refbegin
- Template:Refend
- Template:Short description
- Template:Visible anchor
- Template:Webarchive
- Template:Yes