n-PERMUTABILITY AND LINEAR DATALOG IMPLIES SYMMETRIC DATALOG

Abstrakt

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.

Klíčová slova

• n-PERMUTABILITY
• LINEAR
• IMPLIES
• SYMMETRIC
• DATALOG