BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:8606@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20250306T110000
DTEND;TZID=Europe/Paris:20250306T123000
DTSTAMP:20250305T085353Z
URL:https://www.i2m.univ-amu.fr/evenements/slightly-non-linear-higher-orde
 r-tree-transducers/
SUMMARY:Lê Thành Dũng (Tito) Nguyễn (LIS\, Aix-Marseille): Slightly No
 n-Linear Higher-Order Tree Transducers
DESCRIPTION:Lê Thành Dũng (Tito) Nguyễn: We investigate the tree-to-tr
 ee functions computed by "affine λ-transducers": tree automata whose memo
 ry consists of an affine λ-term instead of a finite state. They can be se
 en as variations on Gallot\, Lemay and Salvati’s Linear High-Order Deter
 ministic Tree Transducers.\nWhen the memory is almost purely affine (à la
  Kanazawa)\, we show that these machines can be translated to tree-walking
  transducers (and with a purely affine memory\, we get a reversible tree-w
 alking transducer). This leads to a proof of an inexpressivity conjecture 
 of Nguyễn and Pradic on "implicit automata" in an affine λ-calculus. We
  also prove that a more powerful variant\, extended with preprocessing by 
 an MSO relabeling and allowing a limited amount of non-linearity\, is equi
 valent in expressive power to Engelfriet\, Hoogeboom and Samwel’s invisi
 ble pebble tree transducers.\nThe key technical tool in our proofs is the 
 Interaction Abstract Machine (IAM)\, an operational avatar of Girard’s g
 eometry of interaction\, a semantics of linear logic. We work with ad-hoc 
 specializations to λ-terms of low exponential depth of a tree-generating 
 version of the IAM.\n\n(J.w.w. Gabriele Vanoni)
CATEGORIES:Séminaire,Logique et Interactions
LOCATION:Luminy - LIS\, salle 04.05\, Campus de Luminy\, Marseille\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=Campus de Luminy\, Marseill
 e\, France;X-APPLE-RADIUS=100;X-TITLE=Luminy - LIS\, salle 04.05:geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20241027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR