k-testable languages with non-constant k?

Question

Let $p_t(w)$ and $s_t(w)$ denote the prefix and suffix of length $t$ of the word $w$, respectively. If $|w| < t$, then $p_t(w) = s_t(w) = w$. Furthermore, let $i_t(w)$ be the set of infixes of length $t$ of $w$. (If $|w| < t$, then $i_t(w)$ is empty.)

For $k \in \mathbb{N}_0$, a language $L \subseteq \Sigma^\ast$ is said to be strictly $k$-testable if there is are sets $P, S \subseteq \Sigma^{\le k}$ and $I \subseteq \Sigma^k$ such that, for every word $w$, $w \in L$ if and only if $p_k(w) \in P$, $s_k(w) \in S$, and $I_k(w) \subseteq I$.

A language is strictly locally testable if it is strictly $k$-testable for some $k$. A language is locally testable if it can be expressed by the union, intersection, or complement of finitely many strictly locally testable languages. It is known that the locally testable languages are a strict subset of the regular languages.

(The above definitions are slightly adapted from here and here.)

Are there any papers which analyse the case in which $k$ is no longer a constant? That is, when $k$ is allowed to scale with the length $|w|$ (but we still have $k \in o(|w|)$; e.g., $k = \log |w|$)? Clearly, the resulting languages will not necessarily be still regular, but they seem to be strongly related to parallel computing models such as cellular automata.

(My Google Scholar searches have been fruitless so far...)

Answer 1

Locally testable languages form a subset of the first-order definable languages, where the only allowed numerical predicate is the successor (see Straubing, page 46 [1]).

By allowing the "local" part to grow, you somehow change the predicate from successor to a length dependent predicate. In particular, the predicate is still "numerical" and thus the languages you are defining are still in $\textrm{AC}^0$ (which is equivalent to FO with the set of all predicates). It is even much lower than that, probably depth-4 wire-linear size circuits, but I didn't check this carefully. I doubt it has a good "cellular automata" variant since it contains a mixture of local (local patterns) and global (alphabet) information. I would be interested to have some insight on the parallel complexity of cellular automata.

My bet is that your class is indeed much more expressive than regular languages, but fails to recognize more regular languages than locally testable ones. To be a bit more formal:

For a sublinear function $f\colon\mathbb{N}\to\mathbb{N}$, let $\textrm{LocTest}_f$ be the class of languages $L$ such that $L\cap A^n$ is a $k$-locally testable language for $k=\mathcal{O}(f(n))$. Then, my guess is that you should have $\textrm{LocTest}_f \cap \textrm{Reg}$ is exactly the class of (classical) locally testable language. This kind of statement can be found for logical framework at the end of Straubing Book (I like to call these properties of classes of languages "Straubing Properties" when it is known and "Straubing Conjecture" when it is open).

For this specific case, I doubt it has been studied as such but it can be seen as a restricted case of the first level of alternation hierarchy of first-order logic with any predicates (which has a known "Straubing Property"). I would bet it should not be too hard to adapt the proof but it requires some heavy semigroups theory results.

[1] Straubing, Howard. Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Birkhäuser Boston, Inc., Boston, MA, 1994.