BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Alexander Rubtsov (HSE University\, Russia)
DTSTART:20251105T140000Z
DTEND:20251105T150000Z
DTSTAMP:20260423T021245Z
UID:FLAT/14
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/FLAT/14/">Co
 mputational model for parsing expression grammars</a>\nby Alexander Rubtso
 v (HSE University\, Russia) as part of One FLAT World Seminar\n\n\nAbstrac
 t\nParsing Expression Grammars (PEGs) have recently gained significant pra
 ctical relevance\, being adopted in compilers such as those for Python and
  Zig\, as well as in parsing libraries for many modern programming languag
 es. Despite their popularity\, the computational foundations of PEGs remai
 n less explored than those of classical grammar formalisms.\n\nIn this tal
 k\, I will present a new computational model for PEGs that extends determi
 nistic pushdown automata. This model enables a structural study of Parsing
  Expression Languages (PEL): in particular\, we show that PELs contain the
  Boolean closure of the regular closure of deterministic context-free lang
 uages (DCFLs) and are closed under left concatenation with this class.\n\n
 We also propose a two-way variation of the model. For this version\, we de
 velop a linear-time simulation algorithm\, analogous to Cook’s classical
  algorithm for two-way DPDAs. These results bridge the gap between theoret
 ical and practical aspects of PEGs\, offering a foundation for further com
 plexity-theoretic and algorithmic analysis.\n
LOCATION:https://researchseminars.org/talk/FLAT/14/
END:VEVENT
END:VCALENDAR