Algebraic program analysis (APA) constructs path expressions from a control-flow graph and interprets them in a semantic algebra. Existing work has shown that graph structure, decompositions, and fill-reducing orderings affect APA cost, but does not choose the next state online as elimination evolves. Such methods cannot use expression-level information that emerges during elimination but is absent from the original graph. We treat elimination order as a state-aware control mechanism for symbolic representation growth, ranking each candidate using the current live graph, expression DAG, and closure risk while leaving the elimination update and semantic interpreter unchanged. Across 17,102 intraprocedural liveness functions, our solution reduces PAR-2 by 16.29× relative to Original. Structural reduces PAR-2 by 5.17× relative to the same baseline. These results suggest that online ordering is an effective complement to purely structural ordering. It can also be combined with representation sharing and decomposition techniques to build more capable APA engines.

@inproceedings{paperbot12594,
  title = {Order-Aware State Elimination for Algebraic Program Analysis},
  author = {Boxuan Zheng},
  booktitle = {ASE},
  year = {2026},
  doi = {10.1145/3832783.3844570}
}