Decision Support using Finite Automata and Decision Diagrams

This thesis considers the area of constraint programming, more specifically, knowledge compilation for the use in decision support. In particular decision support for configuration problems is considered. The main contributions of the thesis are the following: Decision support on unbounded string domains A technique is presented that offers decision support for CSPs that contain variables on unbounded string domains and constraints with regular language membership tests on the string variables. The technique has been implemented and it is em-pirically shown that the technique can support a real-time response on real-world instances. Comparing decision diagrams We compare acyclic DFAs and MDDs and conclude that the difference between the two in structure as well as in size is negligible. We compare direct-encoded BDDs with log-encoded BDDs and empirically show that a direct encoded BDD is orders of magnitudes larger than a corresponding log-encoded BDD. Further the use of ZBDDs for compiling CSPs is proposed and it is empirically shown that on tight instances, ZBDDs result in smaller representations than BDDs for both log-encoded and direct encoded decision diagrams.