 |
 |
Alexandr Kazda - $n$-permutability and linear Datalog implies symmetric Datalog
lmcs:2029 - Logical Methods in Computer Science, April 25, 2018, Volume 14, Issue 2 - https://doi.org/10.23638/LMCS-14(2:3)2018$n$-permutability and linear Datalog implies symmetric DatalogArticle
Authors: Alexandr Kazda 
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.
Source: arXiv.org:1508.05766
Volume: Volume 14, Issue 2
Published on: April 25, 2018
Accepted on: October 2, 2017
Submitted on: September 14, 2016
Keywords: Computer Science - Computational Complexity, 68Q17, 68R05, 03C05
Funding:
- Source : OpenAIRE Graph
- Discrete Optimization in Computer Vision: Theory and Practice; Funder: European Commission; Code: 616160
Classifications
Mathematics Subject Classification 20201
1 Document citing this article
Consultation statistics
This page has been seen 3283 times.
This article's PDF has been downloaded 464 times.