{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T08:41:44Z","timestamp":1774946504030,"version":"3.50.1"},"reference-count":38,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2005,4,29]],"date-time":"2005-04-29T00:00:00Z","timestamp":1114732800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"funder":[{"name":"National Science Foundation","award":["9610257"],"award-info":[{"award-number":["9610257"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.2168\/lmcs-1(1:5)2005","type":"journal-article","created":{"date-parts":[[2005,7,13]],"date-time":"2005-07-13T12:15:17Z","timestamp":1121256917000},"source":"Crossref","is-referenced-by-count":30,"title":["Linear Datalog and Bounded Path Duality of Relational Structures"],"prefix":"10.46298","volume":"Volume 1, Issue 1","author":[{"given":"Victor","family":"Dalmau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2005,4,29]]},"reference":[{"key":"10.2168\/LMCS-1(1:5)2005_Abiteboul\/Hull\/Vianu:1995","author":"Abiteboul","year":"1995"},{"key":"10.2168\/LMCS-1(1:5)2005_Chandra\/Merlin:1977","doi-asserted-by":"crossref","unstructured":"A.K. Chandra and P.M. Merlin. Optimal implementation of conjunctive queries in relational databases. In9th Symp. on Theory of Computing (STOC'77), pages 77-90, 1977.","DOI":"10.1145\/800105.803397"},{"key":"10.2168\/LMCS-1(1:5)2005_Cook:1971","doi-asserted-by":"crossref","unstructured":"S.A. Cook. The Complexity of Theorem-Proving Procedures. In3rd Annual ACM Symposium on Theory of Computing, (STOC'71), pages 151-158, 1971.","DOI":"10.1145\/800157.805047"},{"key":"10.2168\/LMCS-1(1:5)2005_Cooper\/Cohen\/Jeavons:1994","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(94)90021-3"},{"key":"10.2168\/LMCS-1(1:5)2005_Creignou\/Khanna\/Sudan:2001","doi-asserted-by":"crossref","unstructured":"N. Creignou, S. Khanna, and M. Sudan.Complexity Classification of Boolean Constraint Satisfaction Problems, volume 7 ofMonographs on Discrete Mathematics and Applications. SIAM, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"10.2168\/LMCS-1(1:5)2005_Dalmau:2000","unstructured":"V. Dalmau. A New Tractable Class of Constraint Satisfaction Problems. In6th International Symposium on Artificial Intelligence and Mathematics, 2000."},{"key":"10.2168\/LMCS-1(1:5)2005_Dalmau:2002","doi-asserted-by":"crossref","unstructured":"V. Dalmau. Constraint satisfaction problems in non-deterministic logarithmic space. In29th International Colloquium on Automata, Languages, and Programming (ICALP'02), pages 414-425, 2002.","DOI":"10.1007\/3-540-45465-9_36"},{"key":"10.2168\/LMCS-1(1:5)2005_Dalmau\/Kolaitis\/Vardi:2002","doi-asserted-by":"crossref","unstructured":"V. Dalmau, P.G. Kolaitis, and M. Vardi. Constraint Satisfaction Problems, Bounded Treewidth, and Finite-Variable Logics. In8th International Conference on Principles and Practice of Constraint Programming (CP'02), pages 310-326.","DOI":"10.1007\/3-540-46135-3_21"},{"key":"10.2168\/LMCS-1(1:5)2005_Dalmau\/Pearson:1999","doi-asserted-by":"crossref","unstructured":"V. Dalmau and J. Pearson. Set Functions and Width1. In5th International Conference on Principles and Practice of Constraint Programming, (CP'99), volume 1713 ofLecture Notes in Computer Science, pages 159-173, Berlin\/New York, 1999. Springer-Verlag.","DOI":"10.1007\/978-3-540-48085-3_12"},{"key":"10.2168\/LMCS-1(1:5)2005_Dechter\/Pearl:1988","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(87)90002-6"},{"key":"10.2168\/LMCS-1(1:5)2005_Feder\/Vardi:03","doi-asserted-by":"crossref","unstructured":"T. Feder and M. Vardi. Homomorphism closed vs. existential positive. In18th IEEE Symposium on Logic in Computer Science (LICS'03), pages 311-320, 2003.","DOI":"10.1109\/LICS.2003.1210071"},{"key":"10.2168\/LMCS-1(1:5)2005_Feder\/Vardi:1998","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"10.2168\/LMCS-1(1:5)2005_Freuder:1985","doi-asserted-by":"publisher","DOI":"10.1145\/4221.4225"},{"key":"10.2168\/LMCS-1(1:5)2005_Gradel:1992","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90149-A"},{"key":"10.2168\/LMCS-1(1:5)2005_Grohe:03","doi-asserted-by":"crossref","unstructured":"M. Grohe. The Complexity of Homomorphism and Constraint Satisfaction Problems seen from the Other Side. InProceedings of the 44th IEEE Symposium on Foundations of Comupter Science, (FOCS'03), pages 552-561, 2003.","DOI":"10.1109\/SFCS.2003.1238228"},{"key":"10.2168\/LMCS-1(1:5)2005_Hell\/Nesetril:1990","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"10.2168\/LMCS-1(1:5)2005_Hell\/Nesetril\/Zhu:1996","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-96-01537-1"},{"key":"10.2168\/LMCS-1(1:5)2005_Hell\/Zhu:1994","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)90235-6"},{"key":"10.2168\/LMCS-1(1:5)2005_Hell\/Zhu:1995","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480192239992"},{"key":"10.2168\/LMCS-1(1:5)2005_Jeavons:1998","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"10.2168\/LMCS-1(1:5)2005_Jeavons\/Cohen\/Cooper:1998","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(98)00022-8"},{"key":"10.2168\/LMCS-1(1:5)2005_Jeavons\/Cohen\/Gyssens:1997","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"10.2168\/LMCS-1(1:5)2005_Kirousis:1993","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(93)90063-H"},{"key":"10.2168\/LMCS-1(1:5)2005_Kolaitis\/Vardi:1995","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1995.1055"},{"key":"10.2168\/LMCS-1(1:5)2005_Kolaitis\/Vardi:2000b","unstructured":"P.G. Kolaitis and M. Vardi. A Game-Theoretic Approach to Constraint Satisfaction. In17th National Conference on Artificial Intelligence (AAAI'00), pages 175-181."},{"key":"10.2168\/LMCS-1(1:5)2005_Kolaitis\/Vardi:1987","doi-asserted-by":"crossref","unstructured":"P.G. Kolaitis and M. Vardi. The Decision Problem for the Probabilities of Higher-Order Properties. In19th Annual ACM Symposium on Theory of Computing, pages 425-435, 1987.","DOI":"10.1145\/28395.28441"},{"key":"10.2168\/LMCS-1(1:5)2005_Kolaitis\/Vardi:2000a","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"10.2168\/LMCS-1(1:5)2005_Krokhin\/Larose:stacs03","doi-asserted-by":"crossref","unstructured":"A. K. Krokhin and B. Larose. Solving order constraints in logarithmic space. In20th Annual Symposium on Theoretical Aspects of Computer Science (STACS'03), pages 379-390, 2003.","DOI":"10.1007\/3-540-36494-3_34"},{"key":"10.2168\/LMCS-1(1:5)2005_Mackworth:1977","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(77)90007-8"},{"key":"10.2168\/LMCS-1(1:5)2005_Montanari:1974","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0255(74)90008-5"},{"key":"10.2168\/LMCS-1(1:5)2005_Montanari\/Rossi:1991","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(91)90059-S"},{"key":"10.2168\/LMCS-1(1:5)2005_Papadimitriou\/Yannakakis:1991","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"10.2168\/LMCS-1(1:5)2005_Robertson\/Seymour:MinorI","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(83)90079-5"},{"key":"10.2168\/LMCS-1(1:5)2005_Schaefer:1978","doi-asserted-by":"crossref","unstructured":"T.J. Schaefer. The Complexity of Satisfiability Problems. InProceedings of the 10th Annual ACM Symposium on Theory of Computing, (STOC'78), pages 216-226, 1978.","DOI":"10.1145\/800133.804350"},{"key":"10.2168\/LMCS-1(1:5)2005_Szendrei:1987","first-page":"251","volume":"51","author":"Szendrei","year":"1987","journal-title":"Acta Sci. Math."},{"key":"10.2168\/LMCS-1(1:5)2005_Ullman:1989","author":"Ullman","year":"1989"},{"key":"10.2168\/LMCS-1(1:5)2005_Beek\/Dechter:1995","doi-asserted-by":"publisher","DOI":"10.1145\/210346.210347"},{"key":"10.2168\/LMCS-1(1:5)2005_Hentenryck\/Deville\/Teng:1992","doi-asserted-by":"crossref","unstructured":"P. van Hentenryck, Y. Deville, and C-M. Teng. A Generic Arc-consistency Algorithm and its Specializations.Artificial Intelligence, 1992.","DOI":"10.1016\/0004-3702(92)90020-X"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2275\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2275\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,2]],"date-time":"2025-01-02T13:25:48Z","timestamp":1735824348000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2275"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,4,29]]},"references-count":38,"URL":"https:\/\/doi.org\/10.2168\/lmcs-1(1:5)2005","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0504027","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0504027","asserted-by":"subject"}],"is-referenced-by":[{"id-type":"doi","id":"10.1007\/978-3-540-92800-3_5","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,4,29]]},"article-number":"2275"}}