Knowledge compilation [6, 5, 14, 8] consists in transforming a problem offline into a form which is tractable online. In this paper, we introduce new structures, based on the notion of interval automaton (IA), adapted to the compilation of problems involving both discrete and continuous variables, and especially of decision policies and transition tables, in the purpose of controlling autonomous systems.

Interval automata can be seen as a generalization of binary decision diagrams (BDDs) insofar as they are rooted DAGs with variable-labelled nodes, with the differences that interval automata are non-deterministic structures whose edges are labelled with closed intervals and whose nodes can have a multiplicity greater than two.

This paper studies the complexity of the queries and transformations classically considered when examining a new compilation language. We show that a particular subset of interval automata, the focusing ones (FIAs), have theoretical capabilities very close to those of DNNFs; they notably support in polytime the main operations needed to handle decision policies online. Experimental results are presented in order to support these claims.