<p>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]).</p>

<p>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 <span class="math-container">$\textrm{AC}^0$</span> (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. </p>

<p>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: </p>

<p>For a sublinear function <span class="math-container">$f\colon\mathbb{N}\to\mathbb{N}$</span>, let <span class="math-container">$\textrm{LocTest}_f$</span> be the class of languages <span class="math-container">$L$</span> such that <span class="math-container">$L\cap A^n$</span> is a <span class="math-container">$k$</span>-locally testable language for <span class="math-container">$k=\mathcal{O}(f(n))$</span>. Then, my guess is that you should have <span class="math-container">$\textrm{LocTest}_f \cap \textrm{Reg}$</span> 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). </p>

<p>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. </p>

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

CC BY-SA 4.0
2019-06-12T14:32:28.407Z
I've taken a look at the Straubing book (thanks for the reference!), but I'm not sure I follow the reasoning behind the languages being in AC0. Indeed, the predicate describing the positions which are tested by the window of size $k$ is still numerical, as you say, but I don't see how to express the allowed infixes, etc., in this way with a FO formula (without operators). At least in the Straubing book, testing the symbol in a numeric position is an atomic formula, so the number thereof must scale with $k$ (and isn't abstracted by the numerical predicate). Would you care to elaborate?
dkaeae
CC BY-SA 4.0
2019-06-15T19:22:55.560Z
Proving that languages of this shape are AC0 can be done directly: 
It is sufficient to "guess" a possible position where the word we look for is and to effectively test it with a small circuits of size $f(n)$. Altogether, it gives you a circuits of depth 3 and size $n*f(n)$. 

On the logical sides, you can see this by encoding the target word directly into numerical predicates. I can elaborate more, but maybe I should edit the answer above ?
C.P.
CC BY-SA 4.0
2019-06-16T11:25:06.427Z
Yes, but what you say seems to assume there is a single infix we are looking for, and the length of which gets larger and larger. That is something more restrictive than what the question is about. What I mean by $k$ scaling with the input is that the sets of prefixes, infixes, and suffixes $P, S, I$ may also increase in size. These are sets with $O(2^k)$ words. Hence, to account for all of this the circuit will actually need size $n 2^{f(n)}$, which is only polynomial if $f \in O(\log n)$.
dkaeae
CC BY-SA 4.0
2019-06-09T16:42:48.923Z
2019-06-09T18:52:44.460Z
2019-06-09T18:52:44.460Z
C.P.
<p>Let <span class="math-container">$p_t(w)$</span> and <span class="math-container">$s_t(w)$</span> denote the prefix and suffix of length <span class="math-container">$t$</span> of the word <span class="math-container">$w$</span>, respectively. If <span class="math-container">$|w| &lt; t$</span>, then <span class="math-container">$p_t(w) = s_t(w) = w$</span>. Furthermore, let <span class="math-container">$i_t(w)$</span> be the set of infixes of length <span class="math-container">$t$</span> of <span class="math-container">$w$</span>. (If <span class="math-container">$|w| &lt; t$</span>, then <span class="math-container">$i_t(w)$</span> is empty.)</p>

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

<p>A language is <em>strictly locally testable</em> if it is strictly <span class="math-container">$k$</span>-testable for some <span class="math-container">$k$</span>. A language is <em>locally testable</em> 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.</p>

<p>(The above definitions are slightly adapted from <a href="https://www.sciencedirect.com/science/article/pii/S0022000072800205" rel="nofollow noreferrer">here</a> and  <a href="https://www.sciencedirect.com/science/article/pii/S0304397598003326" rel="nofollow noreferrer">here</a>.)</p>

<p><strong>Are there any papers which analyse the case in which <span class="math-container">$k$</span> is no longer a constant?</strong> That is, when <span class="math-container">$k$</span> is allowed to scale with the length <span class="math-container">$|w|$</span> (but we still have <span class="math-container">$k \in o(|w|)$</span>; e.g., <span class="math-container">$k = \log |w|$</span>)? 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.</p>

<p>(My Google Scholar searches have been fruitless so far...)</p>

CC BY-SA 4.0
2019-06-07T14:01:41.633Z
Nice language class, never seen it before! There are also non-context-free languages in this class, for example $L = \{ (a^nb^n c^n)^l \mid n \ge 0, l \ge 2^{3n} \}$ with $k = \log |w|$.
StefanH
CC BY-SA 4.0
2019-06-07T14:59:26.430Z
@StefanH Indeed. It also does not admit most unary languages, including $\{ 1^m \}^\ast$ (where $m > 1$ is constant), so it is incomparable to the regular languages.
dkaeae
<reference-request><fl.formal-languages>
k-testable languages with non-constant k?
dkaeae
# k-testable languages with non-constant k?

(Asked by: username_0 on 2019-06-07)

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](https://www.sciencedirect.com/science/article/pii/S0022000072800205) and [here](https://www.sciencedirect.com/science/article/pii/S0304397598003326).)

**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...)

**Tags:** reference-request, fl.formal-languages
> **Comments:**
> **username_1**: Nice language class, never seen it before! There are also non-context-free languages in this class, for example $L = \{ (a^nb^n c^n)^l \mid n \ge 0, l \ge 2^{3n} \}$ with $k = \log |w|$.  
> **username_0**: @StefanH Indeed. It also does not admit most unary languages, including $\{ 1^m \}^\ast$ (where $m > 1$ is constant), so it is incomparable to the regular languages.  

---

## 1 answers

### Answer by username_2 on 2019-06-09. Score: 3

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.

> **Comments:**
> **username_0**: I've taken a look at the Straubing book (thanks for the reference!), but I'm not sure I follow the reasoning behind the languages being in AC0. Indeed, the predicate describing the positions which are tested by the window of size $k$ is still numerical, as you say, but I don't see how to express the allowed infixes, etc., in this way with a FO formula (without operators). At least in the Straubing book, testing the symbol in a numeric position is an atomic formula, so the number thereof must scale with $k$ (and isn't abstracted by the numerical predicate). Would you care to elaborate?  
> **username_2**: Proving that languages of this shape are AC0 can be done directly:  It is sufficient to "guess" a possible position where the word we look for is and to effectively test it with a small circuits of size $f(n)$. Altogether, it gives you a circuits of depth 3 and size $n*f(n)$.   On the logical sides, you can see this by encoding the target word directly into numerical predicates. I can elaborate more, but maybe I should edit the answer above ?  
> **username_0**: Yes, but what you say seems to assume there is a single infix we are looking for, and the length of which gets larger and larger. That is something more restrictive than what the question is about. What I mean by $k$ scaling with the input is that the sets of prefixes, infixes, and suffixes $P, S, I$ may also increase in size. These are sets with $O(2^k)$ words. Hence, to account for all of this the circuit will actually need size $n 2^{f(n)}$, which is only polynomial if $f \in O(\log n)$.  

---

