一句话：在细粒度复杂度框架下确定 CFL 可达性的精确指数，并证明 Dyck-2 的 Ω(n^2.5) 下界。
许多静态程序分析问题可建模为带标签有向图上的上下文无关语言（CFL）可达性。通用解法时间为 O(n^3)，但给定具体 CFL 时，其精确多项式指数以及是否存在中间复杂度仍缺少完整图景。本文从细粒度复杂度出发，在 BMM、k-Clique、APSP、3SUM 等广泛相信的猜想下，为若干 CFL 类及具体 CFL（重点是 Dyck-k 语言）建立条件下界，刻画其精确运行时间。关键结果包括 Dyck-2 可达性的 Ω(n^2.5) 下界，这是首个适用于所有算法的超二次下界，表明 CFL 可达性严格难于布尔矩阵乘法；同时针对以边数 m 为参数的稀疏图，给出 Andersen 指针分析的立方下界，显著强化了已有结果。
Many problems in static program analysis can be modeled as the context-free language (CFL) reachability problem on directed labeled graphs. The CFL reachability problem can be generally solved in time O ( n 3 ), where n is the number of vertices in the graph, with some specific cases that can be solved faster. In this work, we ask the following question: given a specific CFL, what is the exact exponent in the monomial of the running time? In other words, for which cases do we have linear, quadratic or cubic algorithms, and are there problems with intermediate runtimes? This question is inspired by recent efforts to classify classic problems in terms of their exact polynomial complexity, known as fine-grained complexity. Although recent efforts have shown some conditional lower bounds (mostly for the class of combinatorial algorithms), a general picture of the fine-grained complexity landscape for CFL reachability is missing. Our main contribution is lower bound results that pinpoint the exact running time of several classes of CFLs or specific CFLs under widely believed lower bound conjectures (e.g., Boolean Matrix Multiplication, k -Clique, APSP, 3SUM). We particularly focus on the family of Dyck- k languages (which are strings with well-matched parentheses), a fundamental class of CFL reachability problems. Remarkably, we are able to show a Ω( n 2.5 ) lower bound for Dyck-2 reachability, which to the best of our knowledge is the first super-quadratic lower bound that applies to all algorithms, and shows that CFL reachability is strictly harder that Boolean Matrix Multiplication. We also present new lower bounds for the case of sparse input graphs where the number of edges m is the input parameter, a common setting in the database literature. For this setting, we show a cubic lower bound for Andersen’s Pointer Analysis which significantly strengthens prior known results.