Johannes Ebbing ; Juha Kontinen ; Julian-Steffen Müller ; Heribert Vollmer - A Fragment of Dependence Logic Capturing Polynomial Time

lmcs:795 - Logical Methods in Computer Science, August 15, 2014, Volume 10, Issue 3 - https://doi.org/10.2168/LMCS-10(3:3)2014
A Fragment of Dependence Logic Capturing Polynomial TimeArticle

Authors: Johannes Ebbing ; Juha Kontinen ORCID; Julian-Steffen Müller ; Heribert Vollmer ORCID

    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.

    https://doi.org/10.2168/LMCS-10(3:3)2014
    Source: arXiv.org:1210.3321
    Volume: Volume 10, Issue 3
    Published on: August 15, 2014
    Imported on: September 12, 2013
    Keywords: Computer Science - Logic in Computer Science, Computer Science - Computational Complexity
    Licence: arXiv.org - Non-exclusive license to distribute

    5 Documents citing this article

    Share and export

    Consultation statistics

    This page has been seen 2083 times.
    This article's PDF has been downloaded 494 times.