Linear Datalog and Bounded Path Duality of Relational Structures

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

Бүрэн тодорхойлолт

Номзүйн дэлгэрэнгүй

Үндсэн зохиолч:	Victor Dalmau
Формат:	Artigo
Хэл сонгох:	Inglês
Хэвлэсэн:	Logical Methods in Computer Science e.V. 2005-04-01
Цуврал:	Logical Methods in Computer Science
Нөхцлүүд:	computer science - logic in computer science computer science - computational complexity f.1.3 f.4.1
Онлайн хандалт:	https://lmcs.episciences.org/2275/pdf
Шошгууд:	Шошго нэмэх Шошго байхгүй, Энэхүү баримтыг шошголох эхний хүн болох!