文章基本信息

标题：A Fragment of Dependence Logic Capturing Polynomial Time
本地全文：下载
作者：Johannes Ebbing ; Juha Kontinen ; Julian-Steffen Müller 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：3
页码：1
DOI：10.2168/LMCS-10(3:3)2014
出版社：Technical University of Braunschweig
摘要：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.
其他关键词：Dependence logic, Horn-formulae, computational complexity, descriptive complexity.