5
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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|$. $\endgroup$ – StefanH Jun 7 '19 at 14:01
  • $\begingroup$ @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. $\endgroup$ – dkaeae Jun 7 '19 at 14:59
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – dkaeae Jun 12 '19 at 14:32
  • $\begingroup$ 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 ? $\endgroup$ – C.P. Jun 15 '19 at 19:22
  • $\begingroup$ 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)$. $\endgroup$ – dkaeae Jun 16 '19 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.