1 Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University2 University of Munich3 University of Uppsala
Higher Order Fixpoint Logic (HFL) is a hybrid of the simply typed λ-calculus and the modal μ-calculus. This makes it a highly expressive temporal logic that is capable of expressing various interesting correctness properties of programs that are not expressible in the modal μ-calculus. This paper provides complexity results for its model checking problem. In particular we consider its fragments HFLk,m which are formed using types of bounded order k and arity m only. We establish k-ExpTime-completeness for model checking each HFLk,m fragment. For the upper bound we reduce the problem to the problem of solving rather large parity games of small index. As a consequence of this we obtain an ExpTime upper bound on the expression complexity of each HFLk,m. The lower bound is established by a reduction from the word problem for alternating (k-1)-fold exponential space bounded Turing Machines. As a corollary we obtain k-ExpTime-completeness for the data complexity of HFLk,m already when m ≥ 4.
Logical Methods in Computer Science, 2007, Vol 3, Issue 2