A fragment of dependence logic capturing polynomial time

DOI10.2168/LMCS-10(3:3)2014zbMATH Open1338.68090arXiv1210.3321MaRDI QIDQ2878749FDOQ2878749

Authors: Johannes Ebbing, Juha Kontinen, Julian-Steffen Müller, Heribert Vollmer 

Publication date: 5 September 2014

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

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 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.

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

Recommendations

• A parameterized view on the complexity of dependence logic
• A parameterized view on the complexity of dependence and independence logic
• Expressivity and Complexity of Dependence Logic
• The complexity of independence-friendly fixpoint logic
• Computer Science Logic
• Complexity of validity for propositional dependence logics
• Complexity of validity for propositional dependence logics
• An NP-complete fragment of fibring logic
• Complexity of finite-variable fragments of EXPTIME-complete logics
• Parameterised complexity of model checking and satisfiability in propositional dependence logic

zbMATH Keywords

computational complexitydependence logicdescriptive complexityHorn-formulae

Mathematics Subject Classification ID

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

Cited In (8)

• Expressivity and Complexity of Dependence Logic
• Boolean dependence logic and partially-ordered connectives
• Polynomials, fragments of temporal logic and the variety DA over traces
• A parameterized view on the complexity of dependence logic
• Tractability frontier of data complexity in team semantics
• Complexity thresholds in inclusion logic
• Polynomials, Fragments of Temporal Logic and the Variety DA over Traces
• On dependence logic

This page was built for publication: A fragment of dependence logic capturing polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878749)