A fragment of dependence logic capturing polynomial time

Show simple item record

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

Files in this item

This item appears in the following Collection(s):

Show simple item record


Search the repository


My Account

Usage Statistics