BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Date iCal//NONSGML kigkonsult.se iCalcreator 2.20.2//
METHOD:PUBLISH
X-WR-CALNAME;VALUE=TEXT:Eventi DIAG
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:STANDARD
DTSTART:20211031T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:calendar.23894.field_data.0@www.diag.uniroma1.it
DTSTAMP:20230208T081432Z
CREATED:20211115T105628Z
DESCRIPTION:The central open question in Descriptive Complexity is whether
there is a logic that characterizes deterministic polynomial-time computat
ions (PTIME) on relational structures. In this talk\, I introduce my work
on this question. I define an algebra of binary relations that is obtained
from first-order logic with fixed points\, FO(FP)\, by a series of transf
ormations that include restricting logical connectives and adding a dynami
c version of Hilbert’s Choice operator Epsilon. The formalism can also be
viewed as a linear-time modal Dynamic logic\, where algebraic expressions
describing “proofs” or “programs” appear inside the modalities. Many typic
al polynomial-time properties such as cardinality\, reachability and those
requiring “mixed” propagations (that include linear equations modulo two)
can be specified in the logic\, and an arbitrary PTIME Turing machine can
be encoded. For each fixed Choice function\, the data complexity of model
checking is in PTIME. However\, there can be exponentially many such func
tions. ``Naive evaluations'' refer to a version of this model checking pro
cedure where the Choice function variable Epsilon is simply treated as a c
onstant. A crucial question is under what syntactic conditions on the alge
braic terms such a naive evaluation works\, that is\, provides a certain a
nswer to the original model checking problem. These conditions\, applied t
o the formalism\, would give us a logic for PTIME. The two views of the fo
rmalism\, as an algebra and as a Dynamic logic\, support application of bo
th automata-theoretic and algebraic techniques to the study of this questi
on.
DTSTART;TZID=Europe/Paris:20211118T150000
DTEND;TZID=Europe/Paris:20211118T160000
LAST-MODIFIED:20211115T110751Z
LOCATION:DIAG\, Aula Magna
SUMMARY:Towards Capturing PTIME with no Counting Construct (but with a vers
ion of Hilbert's Choice operator) - Eugenia Ternovska (Simon Fraser Univer
sity\, Vancouver\, Canada)
URL;TYPE=URI:https://www.diag.uniroma1.it/node/23894
END:VEVENT
END:VCALENDAR