Programming Languages and Tools Lab

We consider two interesting concepts: dimension of a parse tree (Straler number) and the rational index \rho_L of a language L which is defined as an integer function, where \rho_L(n) is the maximum length of the shortest string in the intersection of L and R, over all regular languages R recognized by n-state nondeterministic finite automata (NFA). We investigate the rational index of languages defined by (context-free) grammars with bounded Straler number, and show that it is of polynomial in n.

Speaker: Ekaterina Shemetova (JetBrains Research, SPbAU, SPbSU)

Google Meet: https://meet.google.com/myu-dhmz-gvu