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.ugov-ricerca.uniroma1.it
DTSTAMP:20260408T063208Z
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:http://www.ugov-ricerca.uniroma1.it/node/23894
END:VEVENT
END:VCALENDAR