Logics for XML

This work describes the theoretical and practical foundations of a system for the static analysis of XML processing languages. The system relies on a fixpoint modal logic with converse where models are finite trees. This calculus is expressive enough to capture regular tree types along with multi-directional navigation in trees. The decidability of the logic is proved in time 2^O(n) where n is the size of the input formula. XPath expressions and XML schemas are linearly translated into the logic. Based on these embeddings, several problems of major importance in XML applications are reduced to logical satisfiability. The focus is then given to a sound and complete algorithm for deciding the logic, along with crucial implementation techniques for building an effective solver. Practical experiments using a full system implementation are presented. The system appears efficient in practice for several realistic scenarios. The main application of this work is a new class of static analyzers for programs manipulating XML data. Such analyzers allow to ensure at compile-time valuable properties such as type-safety and optimizations, for safer and more efficient XML processing.