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). ...
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...
Inconsistency Handling in Datalog+/− Ontologies
Inconsistency Handling in Datalog+/− Ontologies
The advent of the Semantic Web has made the problem of inconsistency management especially relevant. Datalog+/− is a family of ontology languages that is in particular us...
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...
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...

