SAT-Solving in Practice, with a Tutorial Example from Supervisory Control

• DOI: 10.1007/s10626-009-0081-8
• Publication Date: 2009-09-09T09:47:10Z
• Authors: Koen Claessen; Niklas Een; Mary Sheeran; Niklas Sörensson; Alexey Voronov; Knut Åkesson
• Keywords: Satisfiability; Bridge (graph theory); Boolean satisfiability problem

Satisfiability solving, the problem of deciding whether the variables of a propositional formula can be assigned in such a way that the formula evaluates to true, is one of the classic problems in computer science. It is of theoretical interest because it is the canonical NP-complete problem. It is of practical interest because modern SAT-solvers can be used to solve many important and practical problems. In this tutorial paper, we show briefly how such SAT-solvers are implemented, and point to some typical applications of them. Our aim is to provide sufficient information (much of it through the reference list) to kick-start researchers from new fields wishing to apply SAT-solvers to their problems. Supervisory control theory originated within the control community and is a framework for reasoning about a plant to be controlled and a specification that the closed-loop system must fulfil. This paper aims to bridge the gap between the computer science community and the control community by illustrating how SAT-based techniques can be used to solve some supervisory control related problems.