JetBrains Research unites scientists working in challenging new disciplines

Seminar: Parallel complexity of CFL-reachability problem

Сontext-free language (CFL) reachability problem is a fundamental problem in static cose analysis. CFL-reachability problem for a context-free grammar G and directed edge-labelled graph D consists of determining for every pair of nodes v and u whether v can reach u via a path labelled by a string in L(G). Whereas it has been shown that CFL-reachability problem is P-complete, there are subclasses of context-free languages and graphs, for which CFL-reachability lies is in NC complexity class.

We will investigate parallel complexity of variants of CFL-reachability problem with interesting subclasses of context-free grammars and graphs. A Boolean circuit for this problem will be presented. We will obtain characteristic affecting the effectiveness of Boolean circuit and will observe lower and upper bounds on its value.

Speaker: Ekaterina Shemetova

02.11.2019, 17:15.

Venue: room 3248, Faculty of Mathematics and Mechanics, Saint Petersburg State University, Stary Peterhof, Universitetski pr., 28