On the Completeness and Complexity of the Lifted Dynamic Junction Tree
  Algorithm
  Lifted inference allows to perform inference in polynomial time w.r.t. domain
sizes. For a lifted algorithm, completeness investigates model classes for
which the algorithm is guaranteed to compute a lifted solution. We contribute,
to the best of our knowledge, the first completeness and complexity analysis
for a temporal lifted algorithm, the so-called lifted dynamic junction tree
algorithm (LDJT). To treat time as a first class citizen, LDJT introduces some
constraints. Given these constraints, we analyse the classes of liftable
models. Further, we show that LDJT has many advantages from a complexity point
of view compared to a propositional temporal inference algorithm w.r.t. domain
sizes. Therefore, LDJT advances the number of models for which inference tasks
can be solved in reasonable time not only from a practically point of view, but
also from a theoretical point of view.
