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

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

The Fine-Grained and Parallel Complexity of Andersen’s Pointer Analysis

April 5

Алгоритм Андерсена является распространенным инструментом для анализа указателей. Но теоретическая сложность данного алгоритма является кубической, что потенциально очень печально для практического применения. Однако, если ввести небольшие ограничения, то анализ указателей Андерсена может быть осуществлен менее, чем за кубическое время (время умножения булевых матриц). На семинаре мы разберем данный алгоритм и узнаем при чем здесь язык Дика на одном типе скобок. Помимо этого, используя инструменты fine-grained complexity, мы получим нижние оценки алгоритма Андерсена для общего и частных случаев, а также поговорим о параллельной сложности этого алгоритма.

Материалы к докладу:Anders Alnor Mathiasen and Andreas Pavlogiannis. 2021. The fine-grained and parallel complexity of andersen's pointer analysis. Proc. ACM Program. Lang. 5, POPL, Article 34 (January 2021), 29 pages. DOI:https://doi.org/10.1145/3434315

Семинар состоится онлайн в 17:30, ссылка на встречу https://meet.google.com/myu-dhmz-gvu.