Universal Algebra seminarExport this event to calendar

Thursday, May 8, 2014 — 3:30 PM EDT

Alexandr Kazda, Vanderbilt University

“What would symmetric Datalog do?”

We will talk about a class of Constraint Satisfaction Problems (CSPs) that can be solved in deterministic logarithmic space using fragments of the Datalog language. Datalog language is a close relative to the more famous Prolog programming language; Datalog programs for CSP can be evaluated in polynomial time, and fragments of Datalog are even less computationally demanding: evaluating so-called linear Datalog can be done in nonderministic logspace, while symmetric Datalog programs only need deterministic logspace to run. We give a brief overview of what does it mean to solve CSP using Datalog, followed by an attempt to characterize relational structures A such that CSP(A) can be solved by symmetric Datalog.

Location 
MC - Mathematics & Computer Building
4206
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
  1. 2019 (199)
    1. December (7)
    2. November (26)
    3. October (19)
    4. September (13)
    5. August (7)
    6. July (12)
    7. June (18)
    8. May (22)
    9. April (11)
    10. March (25)
    11. February (17)
    12. January (22)
  2. 2018 (219)
    1. December (2)
    2. November (32)
    3. October (27)
    4. September (26)
    5. August (4)
    6. July (9)
    7. June (13)
    8. May (17)
    9. April (13)
    10. March (28)
    11. February (27)
    12. January (21)
  3. 2017 (281)
  4. 2016 (335)
  5. 2015 (209)
  6. 2014 (235)
  7. 2013 (251)
  8. 2012 (135)