A Fragment of Dependence Logic Capturing Polynomial Time

In this paper, the authors study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore, they define an even smaller fragment D- Horn and show that over finite successor structures it captures the complexity class P of all sets decidable in polynomial time. Furthermore, they study the question which of their results can generalized to the case of open formulae of D-Horn and so-called downwards monotone polynomial time properties of teams.