Algorithms for Linearly Ordered Boolean Formulas

Abstract

This thesis considers a class of propositional boolean formulas on which various problems related to satisfiability are efficiently solvable by a dynamic programming algorithm. It mainly consists of two larger parts: the first part describes the class of boolean formulas we are interested in and how to find them, and the second part investigates whether this class of formulas have any practical implications.