Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Datalog:
TR07-024 | 5th March 2007
Laszlo Egri, Benoit Larose, Pascal Tesson

Symmetric Datalog and Constraint Satisfaction Problems in Logspace

We introduce symmetric Datalog, a syntactic restriction of linear
Datalog and show that its expressive power is exactly that of
restricted symmetric monotone Krom SNP. The deep result of
Reingold on the complexity of undirected
connectivity suffices to show that symmetric Datalog queries can be
evaluated in logarithmic space. We ... more >>>

ISSN 1433-8092 | Imprint