We show that if $\mathbb A$ is a core relational structure such that CSP($\mathbb A$) can be solved by a linear Datalog program, and $\mathbb A$ is $n$-permutable for some $n$, then CSP($\mathbb A$) can be solved by a symmetric Datalog program (and thus CSP($\mathbb A$) lies in deterministic logspace). At the moment, it is not known for which structures $\mathbb A$ will CSP($\mathbb A$) be solvable by a linear Datalog program. However, once somebody obtains a characterization of linear Datalog, our result immediately gives a characterization of symmetric Datalog.

@article{paperbot410,
  title = {$n$-permutability and linear Datalog implies symmetric Datalog},
  author = {Alexandr Kazda},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 2},
  year = {2018},
  doi = {10.23638/lmcs-14(2:3)2018}
}