Publication at Faculty of Mathematics and Physics |
2018
Abstract
We show that if A is a core relational structure such that CSP(A) can be solved by a linear Datalog program, and A is n-permutable for some n, then CSP(A) can be solved by a symmetric Datalog program (and thus CSP(A) lies in deterministic logspace). At the moment, it is not known for which structures A will CSP(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.