BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:34027da9-feab-44dd-82b5-34664acfaa3b
X-WR-CALNAME:[LX] Sarah Winter
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:34027da9-feab-44dd-82b5-34664acfaa3b
DTSTAMP:20260415T114759Z
CLASS:PUBLIC
DESCRIPTION:** A Regular and Complete Notion of Delay for Streaming String 
 Transducers ** \n\nThe notion of delay between finite transducers is a cor
 e element of numerous fundamental results of transducer theory. The goal o
 f this work is to provide a similar notion for more complex abstract machi
 nes: we introduce a new notion of delay tailored to measure the similarity
  between streaming string transducers (SST). \n\nWe show that our notion i
 s regular: we design a finite automaton that can check whether the delay b
 etween any two SSTs executions is smaller than some given bound. As a cons
 equence\, our notion enjoys good decidability properties: in particular\, 
 while equivalence between non-deterministic SSTs is undecidable\, we show 
 that equivalence up to fixed delay is decidable. Moreover\, we show that o
 ur notion has good completeness properties: we prove that two SSTs are equ
 ivalent if and only if they are equivalent up to some (computable) bounded
  delay. \n\nTogether with the regularity of our delay notion\, it provides
  an alternative proof that SSTs equivalence is decidable. Finally\, the de
 finition of our delay notion is machine-independent\, as it only depends o
 n the origin semantics of SSTs. As a corollary\, the completeness result a
 lso holds for equivalent machine models such as deterministic two-way tran
 sducers\, or MSO transducers.\n\nThis is joint work with Emmanuel Filiot\,
  Ismaël Jecker\, and Christof Löding.
DTSTART;TZID=Europe/Paris:20230316T130000
DTEND;TZID=Europe/Paris:20230316T140000
LOCATION:salle 178
SEQUENCE:0
SUMMARY:[LX] Sarah Winter
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
