BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Mikhail Volkov (Ural Federal University)
DTSTART:20260225T140000Z
DTEND:20260225T150000Z
DTSTAMP:20260423T021235Z
UID:FLAT/17
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/17/">Ad
 versarial synchronization</a>\nby Mikhail Volkov (Ural Federal University)
  as part of One FLAT World Seminar\n\n\nAbstract\nWe study a variant of th
 e synchronization game on finite deterministic\nautomata. In this game\, A
 lice chooses one input letter of an automaton\n$A$ on each of her moves wh
 ile Bob may respond with an arbitrary finite\nword over the input alphabet
  of $A$\; Alice wins if the word obtained by\ninterleaving her letters wit
 h Bob's responses resets $A$. We prove that\nif Alice has a winning strate
 gy in this game on $A$\, then $A$ admits a reset\nword whose length is str
 ictly smaller than the number of states of $A$.\nIn contrast\, for any $k$
 \, we exhibit automata with shortest reset-word\nlength quadratic in the n
 umber of states\, on which Alice nevertheless\nwins a version of the game 
 in which Bob's responses are restricted\nto arbitrary words of length at m
 ost $k$.\n\nWe provide polynomial-time algorithms for deciding the winner 
 in various\nsynchronization games\, and we analyze the relationships betwe
 en variants\nof synchronization games on fixed-size automata.\n\nThis is a
  joint work with Anton Lipin.\n
LOCATION:https://researchseminars.org/talk/FLAT/17/
END:VEVENT
END:VCALENDAR