JetBrains Research unites scientists working in challenging new disciplines

Seminar on Rytter Algorithm: Context-Free Recognition Via Shortest Paths Computation

Rytter algorithm is an algorithm recognizing general context-free languages in O(BM(n)) time, where BM(n) is the time to multiply two n x n Boolean matrices. Algorithm solves a problem with nonassociativity of such semirings in Valiant’s algorithm by replacing nonassociative semirings by associative ones. Rytter shows that CFL recognition is the shortest path computation in a special lattice graph where the weights of edges are elements of an associative semiring of constant size.

Rytter algorithm will be explained and example will be provided.

Supplementary materials:

Wojciech Rytter. Context-free recognition via shortest paths computation: a version of Valiant's algorithm (https://www.sciencedirect.com/science/article/pii/030439759400265K)

Presenter: Ekaterina Shemetova

Date: May 7, 2018

Time: 17:15

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