Исследовательская группа

Лаборатория языковых инструментов

Algebraic Path Problems

15 ноября

Algebraic path problems can be viewed as a single framework for many problems in computer science. Procedures for solving these problems are built using various algebraic structures (semirings). Among such problems, of course, there are graph analysis problems (the shortest path problem, the problem of finding optimal paths for a given objective function, etc.), as well as, for example, the problem of determining a regular language recognized by a finite automaton. In addition, they include some graph analysis problems whose formulations do not directly involve the concept of a path, such as finding all the bridges and articulation points of a graph. Initially, the procedures for solving these problems were developed independently of each other. When the connection between these methods became clear, various attempts were made to find a common theoretical basis for them. At the seminar, we will discuss what algebraic path problems are, what the theory is behind them, and also consider examples of their application in graph theory, network analysis, and static code analysis.

Additional materials: 
 * Gunter Rote - Path Problems in Graphs - 1989;
 * John S. Baras and George Theodorakopoulos - Path Problems in Networks - 2010

Speaker: Rustam Azimov

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