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 |
| _version_ | 1797268632583012352 |
|---|---|
| author | Johannes Ebbing Juha Kontinen Julian-Steffen Müller Heribert Vollmer |
| author_facet | Johannes Ebbing Juha Kontinen Julian-Steffen Müller Heribert Vollmer |
| author_sort | Johannes Ebbing |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:35:34Z |
| format | Article |
| id | doaj.art-72ca468483ab4f468485baebe0749bdb |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:35:34Z |
| publishDate | 2014-08-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-72ca468483ab4f468485baebe0749bdb2024-03-08T09:37:13ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742014-08-01Volume 10, Issue 310.2168/LMCS-10(3:3)2014795A Fragment of Dependence Logic Capturing Polynomial TimeJohannes EbbingJuha Kontinenhttps://orcid.org/0000-0003-0115-5154Julian-Steffen MüllerHeribert Vollmerhttps://orcid.org/0000-0002-9292-1960In 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://lmcs.episciences.org/795/pdfcomputer science - logic in computer sciencecomputer science - computational complexity |
| spellingShingle | Johannes Ebbing Juha Kontinen Julian-Steffen Müller Heribert Vollmer A Fragment of Dependence Logic Capturing Polynomial Time Logical Methods in Computer Science computer science - logic in computer science computer science - computational complexity |
| title | A Fragment of Dependence Logic Capturing Polynomial Time |
| title_full | A Fragment of Dependence Logic Capturing Polynomial Time |
| title_fullStr | A Fragment of Dependence Logic Capturing Polynomial Time |
| title_full_unstemmed | A Fragment of Dependence Logic Capturing Polynomial Time |
| title_short | A Fragment of Dependence Logic Capturing Polynomial Time |
| title_sort | fragment of dependence logic capturing polynomial time |
| topic | computer science - logic in computer science computer science - computational complexity |
| url | https://lmcs.episciences.org/795/pdf |
| work_keys_str_mv | AT johannesebbing afragmentofdependencelogiccapturingpolynomialtime AT juhakontinen afragmentofdependencelogiccapturingpolynomialtime AT juliansteffenmuller afragmentofdependencelogiccapturingpolynomialtime AT heribertvollmer afragmentofdependencelogiccapturingpolynomialtime AT johannesebbing fragmentofdependencelogiccapturingpolynomialtime AT juhakontinen fragmentofdependencelogiccapturingpolynomialtime AT juliansteffenmuller fragmentofdependencelogiccapturingpolynomialtime AT heribertvollmer fragmentofdependencelogiccapturingpolynomialtime |