## Dalmau, Victor - Linear Datalog and Bounded Path Duality of Relational Structures

lmcs:2275 - Logical Methods in Computer Science, April 29, 2005, Volume 1, Issue 1
Linear Datalog and Bounded Path Duality of Relational Structures

Authors: Dalmau, Victor

In this paper we systematically investigate the connections between logics with a finite number of variables, structures of bounded pathwidth, and linear Datalog Programs. We prove that, in the context of Constraint Satisfaction Problems, all these concepts correspond to different mathematical embodiments of a unique robust notion that we call bounded path duality. We also study the computational complexity implications of the notion of bounded path duality. We show that every constraint satisfaction problem $\csp(\best)$ with bounded path duality is solvable in NL and that this notion explains in a uniform way all families of CSPs known to be in NL. Finally, we use the results developed in the paper to identify new problems in NL.

Source : oai:arXiv.org:cs/0504027
DOI : 10.2168/LMCS-1(1:5)2005
Volume: Volume 1, Issue 1
Published on: April 29, 2005
Submitted on: September 22, 2004
Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,F.1.3,F.4.1