  Higher-Order Fixpoint Logic (HFL) is a hybrid of the simply typed\lambda-calculus and the modal \lambda-calculus. This makes it a highlyexpressive temporal logic that is capable of expressing various interestingcorrectness properties of programs that are not expressible in the modal\lambda-calculus.  This paper provides complexity results for its model checking problem. Inparticular we consider those fragments of HFL built by using only types ofbounded order k and arity m. We establish k-fold exponential time completenessfor model checking each such fragment. For the upper bound we use fixpointelimination to obtain reachability games that are singly-exponential in thesize of the formula and k-fold exponential in the size of the underlyingtransition system. These games can be solved in deterministic linear time. As asimple consequence, we obtain an exponential time upper bound on the expressioncomplexity of each such fragment.  The lower bound is established by a reduction from the word problem foralternating (k-1)-fold exponential space bounded Turing Machines. Since thereare fixed machines of that type whose word problems are already hard withrespect to k-fold exponential time, we obtain, as a corollary, k-foldexponential time completeness for the data complexity of our fragments of HFL,provided m exceeds 3. This also yields a hierarchy result in expressive power.
We establish k-fold exponential time completeness for model checking each such fragment. For the upper bound we use fixpoint elimination to obtain reachability games that are singly-exponential in the size of the formula and k-fold exponential in the size of the underlying transition system. These games can be solved in deterministic linear time.