2025/07/12 by Rida Ait El Manssour, Manssour, Rida Ait El, Mahsa Naraghi +5
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Algebraic Geometry (math.AG) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Logic in Computer Science (cs.LO) #Matrix Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2507.09373
openalex publication_date 2025/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.