Algebraic Closure of Matrix Sets Recognized by 1-VASS
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908610772074496 |
|---|---|
| author | Manssour, Rida Ait El Naraghi, Mahsa Shirmohammadi, Mahsa Worrell, James |
| author_facet | Manssour, Rida Ait El Naraghi, Mahsa Shirmohammadi, Mahsa Worrell, James |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09373 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Algebraic Closure of Matrix Sets Recognized by 1-VASS Manssour, Rida Ait El Naraghi, Mahsa Shirmohammadi, Mahsa Worrell, James Formal Languages and Automata Theory Logic in Computer Science Algebraic Geometry 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. |
| title | Algebraic Closure of Matrix Sets Recognized by 1-VASS |
| topic | Formal Languages and Automata Theory Logic in Computer Science Algebraic Geometry |
| url | https://arxiv.org/abs/2507.09373 |