Linear Datalog and Bounded Path Duality of Relational Structures

Victor Dalmau

doi:10.2168/LMCS-1(1:5)2005

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

lmcs:2275 - Logical Methods in Computer Science, April 29, 2005, Volume 1, Issue 1 - https://doi.org/10.2168/LMCS-1(1:5)2005

Linear Datalog and Bounded Path Duality of Relational StructuresArticle

Authors: Victor Dalmau

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.

https://doi.org/10.2168/LMCS-1(1:5)2005

Source: arXiv.org:cs/0504027

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

Licence: arXiv.org - Assumed non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Aspects of Computation Theory and Logic; Funder: National Science Foundation; Code: 9610257

Bibliographic References

34 Documents citing this article

Manuel Bodirsky;Jakub Bulín;Florian Starke;Michael Wernthaler, 2023, The smallest hard trees, Constraints, 28, 2, pp. 105-137, 10.1007/s10601-023-09341-8, https://doi.org/10.1007/s10601-023-09341-8.

Carsten Lutz;Leif Sabellek, 2022, A complete classification of the complexity and rewritability of ontology-mediated queries based on the description logic EL, arXiv (Cornell University), 308, pp. 103709, 10.1016/j.artint.2022.103709, https://arxiv.org/abs/1904.12533.

Manuel Bodirsky;Florian Starke, 2022, Maximal Digraphs with Respect to Primitive Positive Constructability, arXiv (Cornell University), 42, S1, pp. 997-1010, 10.1007/s00493-022-4918-1, http://arxiv.org/abs/2103.08625.

Yoàv Montacute;Nihil Shah, Apollo (University of Cambridge), The Pebble-Relation Comonad in Finite Model Theory, 2022, Haifa Israel, 10.1145/3531130.3533335, https://www.repository.cam.ac.uk/handle/1810/343297.

Eleni Bakali;Aggeliki Chalki;Aris Pagourtzis, Lecture notes in computer science, Characterizations and Approximability of Hard Counting Classes Below $$\#\mathsf {P}$$, pp. 251-262, 2020, 10.1007/978-3-030-59267-7_22.

Víctor Dalmau;Marcin Kozik;Andrei Krokhin;Konstantin Makarychev;Yury Makarychev;et al., 2019, Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs, Repositori digital de la UPF (Universitat Pompeu Fabra), 48, 6, pp. 1763-1795, 10.1137/18m1163932, https://hdl.handle.net/10230/43659.

Hubie Chen;Moritz Müller, 2017, One Hierarchy Spawns Another, BIROn (Birkbeck, University of London), 18, 4, pp. 1-37, 10.1145/3143805, https://eprints.bbk.ac.uk/id/eprint/21940/1/1307.1353.pdf.

Victor Dalmau;Laszlo Egri;Pavol Hell;Benoit Larose;Arash Rafiey, 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, Descriptive Complexity of List H-Coloring Problems in Logspace: A Refined Dichotomy, 80, pp. 487-498, 2015, Kyoto, Japan, 10.1109/lics.2015.52.

Hubie Chen;Moritz Müller, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), One hierarchy spawns another, pp. 1-10, 2014, Vienna Austria, 10.1145/2603088.2603107.

Víctor Dalmau;Andrei Krokhin, 2013, Robust Satisfiability for CSPs, Durham Research Online (Durham University), 5, 4, pp. 1-25, 10.1145/2540090, https://dro.dur.ac.uk/12625/.

Leslie Ann Goldberg;Mark Jerrum, 2012, Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials, Journal of Computer and System Sciences, 79, 1, pp. 68-78, 10.1016/j.jcss.2012.04.005, https://doi.org/10.1016/j.jcss.2012.04.005.

Leslie Ann Goldberg;Mark Jerrum, 2012, Approximating the partition function of the ferromagnetic Potts model, arXiv (Cornell University), 59, 5, pp. 1-31, 10.1145/2371656.2371660, http://arxiv.org/abs/1002.0986.

Libor Barto;Marcin Kozik;Ross Willard, 2012 27th Annual IEEE Symposium on Logic in Computer Science, Near Unanimity Constraints Have Bounded Pathwidth Duality, 113, pp. 125-134, 2012, Dubrovnik, Croatia, 10.1109/lics.2012.24.

Prasad Chebolu;Leslie Ann Goldberg;Russell Martin, 2012, The complexity of approximately counting stable roommate assignments, Journal of Computer and System Sciences, 78, 5, pp. 1579-1605, 10.1016/j.jcss.2012.02.003, https://doi.org/10.1016/j.jcss.2012.02.003.

Prasad Chebolu;Leslie Ann Goldberg;Russell Martin, 2012, The complexity of approximately counting stable matchings, Theoretical Computer Science, 437, pp. 35-68, 10.1016/j.tcs.2012.02.029, https://doi.org/10.1016/j.tcs.2012.02.029.

Catarina Carvalho;László Egri;Marcel Jackson;Todd Niven, University of Hertfordshire Research Archive (University of Hertfordshire), On Maltsev Digraphs, pp. 181-194, 2011, 10.1007/978-3-642-20712-9_14, http://hdl.handle.net/2299/16610.

László Egri;Andrei Krokhin;Benoit Larose;Pascal Tesson, 2011, The Complexity of the List Homomorphism Problem for Graphs, Leibniz-Zentrum für Informatik (Schloss Dagstuhl), 51, 2, pp. 143-178, 10.1007/s00224-011-9333-8, https://drops.dagstuhl.de/opus/volltexte/2010/2467/.

Catarina Carvalho;Víctor Dalmau;Andrei Krokhin, 2010, CSP duality and trees of bounded pathwidth, Theoretical Computer Science, 411, 34-36, pp. 3188-3208, 10.1016/j.tcs.2010.05.016, https://doi.org/10.1016/j.tcs.2010.05.016.

Leslie Ann Goldberg;Mark Jerrum, arXiv (Cornell University), Approximating the Partition Function of the Ferromagnetic Potts Model, pp. 396-407, 2010, 10.1007/978-3-642-14165-2_34, http://arxiv.org/abs/1002.0986.

Prasad Chebolu;Leslie Ann Goldberg;Russell Martin, Lecture notes in computer science, The Complexity of Approximately Counting Stable Matchings, pp. 81-94, 2010, 10.1007/978-3-642-15369-3_7.

Albert Atserias;Andrei Bulatov;Anuj Dawar, 2009, Affine systems of equations and counting infinitary logic, Theoretical Computer Science, 410, 18, pp. 1666-1683, 10.1016/j.tcs.2008.12.049, https://doi.org/10.1016/j.tcs.2008.12.049.

Benoît Larose;Pascal Tesson, 2009, Universal algebra and hardness results for constraint satisfaction problems, Theoretical Computer Science, 410, 18, pp. 1629-1647, 10.1016/j.tcs.2008.12.048, https://doi.org/10.1016/j.tcs.2008.12.048.

Hubie Chen, 2009, A rendezvous of logic, complexity, and algebra, ACM Computing Surveys, 42, 1, pp. 1-32, 10.1145/1592451.1592453.

Andrei A. Bulatov;Andrei Krokhin;Benoit Larose, CiteSeer X (The Pennsylvania State University), Dualities for Constraint Satisfaction Problems, pp. 93-124, 2008, 10.1007/978-3-540-92800-3_5, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.111.7001.

Catarina Carvalho;Víctor Dalmau;Andrei Krokhin, Proceedings - Symposium on Logic in Computer Science, Caterpillar Duality for Constraint Satisfaction Problems, 4162, pp. 307-316, 2008, Pittsburgh, PA, USA, 10.1109/lics.2008.19, https://dro.dur.ac.uk/6679/1/6679.pdf.

Eric Allender;Michael Bauland;Neil Immerman;Henning Schnoor;Heribert Vollmer, 2008, The complexity of satisfiability problems: Refining Schaefer's theorem, Journal of Computer and System Sciences, 75, 4, pp. 245-254, 10.1016/j.jcss.2008.11.001, https://doi.org/10.1016/j.jcss.2008.11.001.

László Egri;Benoît Larose;Pascal Tesson, Lecture notes in computer science, Directed st-Connectivity Is Not Expressible in Symmetric Datalog, pp. 172-183, 2008, 10.1007/978-3-540-70583-3_15.

Victor Dalmau;Benoit Larose, Proceedings - Symposium on Logic in Computer Science, Maltsev + Datalog --&#x226B; Symmetric Datalog, 76, pp. 297-306, 2008, Pittsburgh, PA, USA, 10.1109/lics.2008.14.

Víctor Dalmau;Andrei Krokhin, 2008, Majority constraints have bounded pathwidth duality, European Journal of Combinatorics, 29, 4, pp. 821-837, 10.1016/j.ejc.2007.11.020, https://doi.org/10.1016/j.ejc.2007.11.020.

Albert Atserias;Andrei Bulatov;Anuj Dawar, Lecture notes in computer science, Affine Systems of Equations and Counting Infinitary Logic, pp. 558-570, 2007, 10.1007/978-3-540-73420-8_49.

Benoît Larose;Pascal Tesson, Lecture notes in computer science, Universal Algebra and Hardness Results for Constraint Satisfaction Problems, pp. 267-278, 2007, 10.1007/978-3-540-73420-8_25, https://doi.org/10.1007/978-3-540-73420-8_25.

Laszlo Egri;Benoit Larose;Pascal Tesson, 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007), Symmetric Datalog and Constraint Satisfaction Problems in Logspace, 2007, Wroclaw, Poland, 10.1109/lics.2007.47.

David Cohen;Peter Jeavons, Oxford University Research Archive (ORA) (University of Oxford), The Complexity of Constraint Languages, pp. 245-280, 2006, 10.1016/s1574-6526(06)80012-x, https://ora.ox.ac.uk/objects/uuid:565b1b9f-bdc4-4332-82f4-cf0e3f54d815.

Hubie Chen, 2006, A rendezvous of logic, complexity, and algebra, arXiv (Cornell University), 37, 4, pp. 85-114, 10.1145/1189056.1189076.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1485 times.

This article's PDF has been downloaded 317 times.