Animation scientifique
Date : 2 juillet 2026 14:30 - Salle :Salle A111
On the Algebraic Closure of Context-Free Matrix LanguagesMahsa Naraghi - IRIF Groupe de travail : ALCOLOCO |
Let L be a language over a finite set of symbols, and let f be a mapping that assigns to each string of symbols a square matrix with rational entries in a way that respects concatenation. We are interested in whether it is possible to effectively compute the algebraic closure of the set of matrices generated by applying f to all strings in the language. It was recently shown that this closure can be computed when the language is regular.
In this talk, we show the computability of this closure for 1-VASS coverability and reachability languages, and we discuss extensions of these results to families of context-free languages. Mainly, I will focus on languages determined by finite-index grammars.
This work is in collaboration with Rida Ait El Manssour, Mahsa Shirmohammadi, and James Worrell.
This work is in collaboration with Rida Ait El Manssour, Mahsa Shirmohammadi, and James Worrell.