Symmetric Datalog and constraint satisfaction problems in logspace

被引:19
作者
Egri, Laszlo [1 ]
Larose, Benoit [2 ]
Tesson, Pascal [3 ]
机构
[1] McGill Univ, Montreal, PQ H3A 2T5, Canada
[2] Concordia Univ, Montreal, PQ, Canada
[3] Univ Laval, Quebec City, PQ G1K 7P4, Canada
来源
22ND ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS | 2007年
基金
加拿大自然科学与工程研究理事会;
关键词
D O I
10.1109/LICS.2007.47
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We introduce symmetric Datalog, a syntactic restriction of linear Datalog and show that its expressive power is exactly that of restricted symmetric Krom monotone SNP The deep result of Reingold [171 on the complexity of undirected connectivity suffices to show that symmetric Datalog queries can be evaluated in logarithmic space. We show that for a number of constraint languages IF, the complement of the constraint satisfaction problem CSP(Gamma) can be expressed in symmetric Datalog. In particular, we show that if CSP(Gamma) is first-order definable and A is a finite subset of the relational clone generated by F then -> CSP(Lambda) is definable in symmetric Datalog. Over the two-element domain and under standard complexity-theoretic assumptions, expressibility of -> CSP(Lambda) in symmetric Datalog corresponds exactly to the class of CSPs computable in logarithmic space. Finally, we describe a fairly general subclass of implicational (or 0/1/all) constraints for which the complement of the corresponding CSP is also definable in symmetric Datalog. Our results provide preliminary evidence that symmetric Datalog may be a unifying explanationforfamilies of CSPs lying in L.
引用
收藏
页码:193 / +
页数:2
相关论文
共 20 条
  • [1] ALLENDER E, 2005, P 30 INT S MATH FDN, P71
  • [2] Atserias A, 2005, IEEE S LOG, P106
  • [3] Tractable conservative constraint satisfaction problems
    Bulatov, AA
    [J]. 18TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, PROCEEDINGS, 2003, : 321 - 330
  • [4] Bulatov AA, 2002, ANN IEEE SYMP FOUND, P649, DOI 10.1109/SFCS.2002.1181990
  • [5] Cohen D, 2006, FOUND ARTIF INTELL, P245
  • [6] CHARACTERIZING TRACTABLE CONSTRAINTS
    COOPER, MC
    COHEN, DA
    JEAVONS, PG
    [J]. ARTIFICIAL INTELLIGENCE, 1994, 65 (02) : 347 - 361
  • [7] Dalmau V., 2002, Principles and Practice of Constraint Programming - CP 2002. 8th International Conference, CP 2002. Proceedings (Lecture Notes in Computer Science Vol.2470), P310
  • [8] DALMAU V, 2007, LIMITS EXPRESSIVITY
  • [9] LINEAR DATALOG AND BOUNDED PATH DUALITY OF RELATIONAL STRUCTURES
    Dalmau, Victor
    [J]. LOGICAL METHODS IN COMPUTER SCIENCE, 2005, 1 (01)
  • [10] The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory
    Feder, T
    Vardi, MY
    [J]. SIAM JOURNAL ON COMPUTING, 1998, 28 (01) : 57 - 104