Algebraic closure of matrix sets recognized by 1-VASS

Conference item

It is known how to compute the Zariski closure of a finitely generated monoid of matrices and, more generally, of a set of matrices specified by a regular language. This result was recently used to give a procedure to compute all polynomial invariants of a given affine program. Decidability of the more general problem of computing all polynomial invariants of affine programs with recursive procedure calls remains open. Mathematically speaking, the core challenge is to compute the Zariski closure of a set of matrices defined by a context-free language. In this paper, we approach the problem from two sides: Towards decidability, we give a procedure to compute the Zariski closure of sets of matrices given by one-counter languages (that is, languages accepted by one-dimensional vector addition systems with states and zero tests), a proper subclass of context-free languages. On the other side, we show that the problem becomes undecidable for indexed languages, a natural extension of context-free languages corresponding to nested pushdown automata. One of our main technical tools is a novel adaptation of Simon’s factorization forests to infinite monoids of matrices.

Authors: Ait El Manssour, R; Naraghi, M; Shirmohammadi, M; Worrell, J

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• Pages: 5211-5240
• Publication date: 2026-01-01
• Acceptance date: 2025-10-23
• Event title: ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)
• Event location: Vancouver, Canada
• Event website: https://www.siam.org/conferences-events/siam-conferences/soda26/
• Event start date: 2026-01-11
• Event end date: 2026-01-14
• DOI: 10.1137/1.9781611978971
• ISBN: 9781611978971
• Language: English