BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:226d0bea-9a65-4b8e-978f-80753767a4f3
X-WR-CALNAME:[M2F] Rémi Morvan
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20241027T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20221030T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20231029T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20220327T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20230326T020000
RDATE:20240331T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:226d0bea-9a65-4b8e-978f-80753767a4f3
DTSTAMP:20260917T192250Z
CLASS:PUBLIC
DESCRIPTION:** Approximation and Semantic Tree-width of Conjunctive Regular
  Path Queries **\n\nWe show that the problem of whether a query is equival
 ent to a query of tree-width k is decidable\, for the class of Unions of C
 onjunctive Regular Path Queries with two-way navigation (UC2RPQs). A previ
 ous result by Barceló\, Romero\, and Vardi has shown decidability for the 
 case k=1\, and here we show that decidability in fact holds for any arbitr
 ary k>1. The algorithm is in 2ExpSpace\, but we show that the complexity d
 rops to the second level of the polynomial hierarchy for a restricted but 
 practically relevant case of queries obtained by only allowing simple regu
 lar expressions.\nWe also investigate the related problem of approximating
  a UC2RPQ by queries of small tree-width. We exhibit an algorithm which\, 
 for any fixed number k\, builds the maximal under-approximation of tree-wi
 dth k of a UC2RPQ. The maximal under-approximation of tree-width k of a qu
 ery q is a query q' of tree-width k which is contained in q in a maximal a
 nd unique way\, that is\, such that for every query q'' of tree-width k\, 
 if q'' is contained in q then q'' is also contained in q'. Joint work with
  Diego Figueira.
DTSTART;TZID=Europe/Paris:20221206T140000
DTEND;TZID=Europe/Paris:20221206T150000
LOCATION:LaBRI
SEQUENCE:0
SUMMARY:[M2F] Rémi Morvan
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR