On Two-Sided Locally Testable Languages
Martin Kutrib, Friedrich Otto · Journal of automata, languages and combinatorics · 2020
We extend the two-sided strictly locally testable languages to the two-sided locally testable languages, showing that for each integer $k\ge 1$ and each symmetric binary relation $R$ on $\Sigma^k$, the family $2LT_R(k)$ of $k$-$R$-testable languages is obtained as a special kind of Boolean closure of the family of two-sided strictly $k$-testable languages. We further study closure and non-closure properties, prove that all two-sided locally testable languages are even linear languages that are learnable in the limit from positive data, and we study decision problems for two-sided locally testable languages.