2008 23rd Annual IEEE Symposium on Logic in Computer Science Maltsev + Datalog --> Symmetric Datalog June 24-June 27 ISBN: 978-0-7695-3183-0
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2008.14
Let B be a finite, core relational structureand let A be the algebra associated to B, i.e.whose terms are the operations on the universeof B that preserve the relations of B. Weshow that if A generates a so-called arithmetical variety then CSP(B), the constraint satisfaction problem associated to B, is solvable inLogspace; in fact??CSP(B) is expressible insymmetric Datalog. In particular, we obtainthat if??CSP(B) is expressible in Datalog andthe relations of B are invariant under a Maltsevoperation then CSP(B) is in symmetric Datalog.
Index Terms:
Maltsev term, Dstalog, Symmetric Datalog
Citation:
Victor Dalmau, Benoit Larose, "Maltsev + Datalog --> Symmetric Datalog," lics, pp.297-306, 2008 23rd Annual IEEE Symposium on Logic in Computer Science, 2008 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb