dc.identifier.uri |
http://dx.doi.org/10.15488/1980 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2005 |
|
dc.contributor.author |
Ebbing, Johannes
|
|
dc.contributor.author |
Kontinen, Juha
|
|
dc.contributor.author |
Mueller, Julian-Steffen
|
|
dc.contributor.author |
Vollmer, Heribert
|
|
dc.date.accessioned |
2017-10-10T07:24:36Z |
|
dc.date.available |
2017-10-10T07:24:36Z |
|
dc.date.issued |
2014 |
|
dc.identifier.citation |
Ebbing, Johannes; Kontinen, Juha; Mueller, Julian-Steffen; Vollmer, Heribert: A fragment of dependence logic capturing polynomial time. In: Logical Methods in Computer Science 10 (2014), Nr. 3, 3. DOI: https://doi.org/10.2168/LMCS-10(3:3)2014 |
|
dc.description.abstract |
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 show that the open D*-Horn-formulae correspond to the negative fragment of SO there exists-Horn. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Braunschweig : Tech. Univ. Braunschweig |
|
dc.relation.ispartofseries |
Logical Methods in Computer Science 10 (2014), Nr. 3 |
|
dc.rights |
CC BY-ND 2.0 Unported |
|
dc.rights.uri |
https://creativecommons.org/licenses/by-nd/2.0/ |
|
dc.subject |
dependence logic |
eng |
dc.subject |
horn-formulae |
eng |
dc.subject |
computational complexity |
eng |
dc.subject |
descriptive complexity |
eng |
dc.subject |
complexity |
eng |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.title |
A fragment of dependence logic capturing polynomial time |
eng |
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
1860-5974 |
|
dc.relation.doi |
https://doi.org/10.2168/LMCS-10(3:3)2014 |
|
dc.bibliographicCitation.issue |
3 |
|
dc.bibliographicCitation.volume |
10 |
|
dc.bibliographicCitation.firstPage |
3 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|