Closure of varieties of languages under products with counter (Q1201878): Difference between revisions

Let \(L_ 0,\dots,L_ k\) be languages over some alphabet \(A\), let \(a_ 1,\dots,a_ k\) be letters of \(A\), let \(r,t\in\mathbb{N}\) and let \(n\in\mathbb{N}- \{0\}\). The product with counter \(r,n,t\) of these languages is then the language denoted \((L_ 0a_ 1L_ 1\dots a_ kL_ k)_{r,n,t}\) that consists in the words \(w\) such that the number of factorizations of the form \(w=u_ 0a_ 1u_ 1\dots a_ ku_ k\) with \(u_ i\in L_ i\) is congruent to \(r\) mod \(n\) threshold \(t\). This paper is essentially devoted to the characterization and the study of the fine structure of the language varieties in the sense of Eilenberg that are closed under product with counter. Some decidability results for these kinds of varieties are also given at the end of the paper.