A Fragment of Dependence Logic Capturing Polynomial Time
In this paper we study the expressive power of Horn-formulae in dependence logic and show that they can express NP-complete problems. Therefore we 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 polyno...
Main Authors: | , , , |
---|---|
Format: | Article |
Language: | English |
Published: |
Logical Methods in Computer Science e.V.
2014-08-01
|
Series: | Logical Methods in Computer Science |
Subjects: | |
Online Access: | https://lmcs.episciences.org/795/pdf |
Summary: | In this paper we study the expressive power of Horn-formulae in dependence
logic and show that they can express NP-complete problems. Therefore we 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 we study the question which of our results can ge generalized to
the case of open formulae of D-Horn* and so-called downwards monotone
polynomial time properties of teams. |
---|---|
ISSN: | 1860-5974 |