Some variations on the notion of locally testable language (Q2709036)

For nonnegative integers \(k\) and \(n\) define \(i\equiv_{k,n}j\) if \(i=j\) or \(i,j\geq k\) and \(|i-j|\) is divisible by \(n\). For a non-empty word \(u\) over an alphabet \(A\), let \(|u|\) denote the length of \(u\), and if \(|u|\leq k\) then define \(i_k(u)=t_k(u)=u\), if \(|u|>k\) then define \(i_k(u)\) (or \(t_k(u)\)) as the prefix (or the suffix) of \(u\) of length \(k\).NEWLINENEWLINENEWLINEFor words \(u,v\in A^+\), let \(\binom uv\) denote the number of occurences of \(v\) in \(u\). For \(k,n\geq 1\) and \(t\geq 0\) define an equivalence \(\equiv_{k,t,n}\) (or \(\approx_{k,t,n}\), or \(\sim_{k,t,n}\)) over \(A^+\) such that \(u\equiv_{k,t,n}v\) (or \(u\approx_{k,t,n}v\), or \(u\sim_{k,t,n}v\)) if \(\binom ux\equiv_{t,n}\binom vx\) for all words \(x\) of length \(\leq k\) (or \(u\equiv_{k,t,n}v\) and \(i_{k-1}(u)=i_{k-1}(v)\), or \(u\approx_{k,t,n}v\) and \(t_{k-1}(u)=t_{k-1}(v)\)). A language \(L\) over \(A^+\) is called locally testable (or strongly locally testable, or locally testable by prefixes, or threshold locally testable, or strongly threshold locally testable, or threshold locally testable by prefixes, or counting locally testable, or strongly counting locally testable, or counting locally testable by prefixes) if \(L\) is saturated by \(\sim_{k,1,1}\) (or \(\equiv_{k,1,1}\), or \(\approx_{k,1,1}\), or \(\sim_{k,t,1}\), or \(\equiv_{k,t,1}\), or \(\approx_{k,t,1}\), or \(\sim_{k,t,n}\), or \(\equiv_{k,t,n}\), or \(\approx_{k,t,n}\)) for some integers \(k,t,n\geq 1\). All classes of languages defined are closed under Boolean operations (sets of generators of these Boolean algebras are given) but a variety of languages form only the classes of locally testable languages, of threshold locally testable languages and of counting testable languages. For any defined class \(\mathcal C\) of languages that is not a variety of languages the least variety of languages containing \(\mathcal C\) and the greatest variety of languages contained in \(\mathcal C\) are given.NEWLINENEWLINEFor the entire collection see [Zbl 0954.00028].