A Fragment of Dependence Logic Capturing Polynomial Time

DOI10.2168/LMCS-10(3:3)2014zbMath1338.68090arXiv1210.3321MaRDI QIDQ2878749

Heribert Vollmer, Juha Kontinen, Johannes Ebbing, Julian Müller

Publication date: 5 September 2014

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1210.3321

zbMATH Keywords

computational complexitydependence logicdescriptive complexityHorn-formulae

Mathematics Subject Classification ID

Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items (5)

Boolean dependence logic and partially-ordered connectives ⋮ Unnamed Item ⋮ Expressivity and Complexity of Dependence Logic ⋮ Complexity thresholds in inclusion logic ⋮ On Dependence Logic

This page was built for publication: A Fragment of Dependence Logic Capturing Polynomial Time