Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
Javascript must be enabled to continue!

$n$-permutability and linear Datalog implies symmetric Datalog

View through CrossRef
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.
Centre pour la Communication Scientifique Directe (CCSD)
Title: $n$-permutability and linear Datalog implies symmetric Datalog
Description:
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.

Related Results

Data functions, datalog and negation
Data functions, datalog and negation
Datalog is extended to incorporate single-valued “data functions”, which correspond to attributes in semantic models, and which may be base (user-specified) or derived (computed). ...
ON TEMPORAL DEDUCTIVE DATABASES
ON TEMPORAL DEDUCTIVE DATABASES
This article introduces a temporal deductive database system featuring a logic programming language and an algebraic front‐end. The language, called Temporal DATALOG, is an extensi...
Tractable Reasoning with DL-Programs over Datalog-rewritable Description Logics
Tractable Reasoning with DL-Programs over Datalog-rewritable Description Logics
The deployment of KR formalisms to the Web has created the need for formalisms that combine heterogeneous knowledge bases. Nonmonotonic dl-programs provide a loose integration of D...
A Differential Datalog Interpreter 
A Differential Datalog Interpreter 
The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. T...
Software Product Line Analysis Using Variability-aware Datalog
Software Product Line Analysis Using Variability-aware Datalog
Applying program analyses to Software Product Lines (SPLs) has been a fundamental research problem at the intersection<br>of Product Line Engineering and software analysis. D...
Software Product Line Analysis Using Variability-aware Datalog
Software Product Line Analysis Using Variability-aware Datalog
Applying program analyses to Software Product Lines (SPLs) has been a fundamental research problem at the intersection<br>of Product Line Engineering and software analysis. D...
Forecasting, When Power Law Distributions Apply
Forecasting, When Power Law Distributions Apply
<p>Whilst a lot of our strategic focus in the public sector is on linear policy approaches, many systems/ phenomena of importance are defined as non-linear or far from equili...
A Symmetric-Actuating Linear Piezoceramic Ultrasonic Motor Capable of Producing a Scissoring Effect
A Symmetric-Actuating Linear Piezoceramic Ultrasonic Motor Capable of Producing a Scissoring Effect
Conventionally, to produce a linear motion, one motor’s stator is employed to drive one runner moving forward or backward. So far, there is almost no report of one electromechanica...

Back to Top