A Fragment of Dependence Logic Capturing Polynomial Time
From MaRDI portal
Publication:2878749
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
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
