3
$\begingroup$

A language $L \subseteq X^*$ is non-counting of order $n > 0$ iff for all $u,v, w \in X^*$ $$ uv^nw \in L \Leftrightarrow uv^{n+1} w \in L. $$ A $\omega$-language (set of infinite sequences) $L \subseteq X^{\omega}$ is non-counting of order $n > 0 $ iff for all $u,v \in X^*, \eta \in X^{\omega}$ $$ uv^{n}\eta \in L \Leftrightarrow uv^{n+1} \eta \in L. $$

When talking about languages over finite words, i.e. subsets $L$ of $X^*$ every regular, noncounting languages of order $n > 0$ fullfills the following property: Let $u,v \in X^*$ with $$ P_n(u) = P_n(v), I_n(u) = I_n(v), S_n(u) = S_n(v) $$ and $u \in L$ (where $P_n, S_n, I_n$ denote the prefix, suffix and infixes of length $n$) then also $v \in L$, meaning if two words coincide in their prefix, suffix and infixes of fixed length $n > 0$ then they are either both in $L$ or both not in $L$.

Now when considering subsets of infinite words (and so just prefix and infixes), i.e. $L \subseteq X^{\mathbb N}$, then this does not hold any longer. For consider $L = X^* 0^{\omega}$, then $L$ is regular and non-counting for each $n > 0$. Fix some $n > 0$ and consider $$ \xi = 0^n1^n0^{\omega} \quad \mbox{ and } \quad \eta = 0^n1^n0^n1^{\omega} $$ then $P_n(\xi) = P_n(\eta)$ and $I_n(\xi) = I_n(\eta)$ but $\xi \in L$ and $\eta\notin L$.

The space $X^{\omega}$ is naturally topologized as the Cantor space, i.e. the space with the common-prefix-metric, or equivalently generated by the basis $v\cdot X^{\omega}$, $v \in X^*$. Now the set $L = X^* 0^{\omega}$ is not closed in Cantor space, for example $1^n0^{\omega}$ is in $L$, but its limit $1^{\omega}$ is not in $L$. So I conjecture that if $L$ is closed then the property from finite sets also hold for infinite sequences, i.e. if $L$ is regular and non-counting, then if two words coinside in their prefix and infixes of some specified length, then they are either both in $L$ or not both. A language $L$ is closed in Cantor space iff if it has the property that if $\xi$ is such that every prefix of $\xi$ is the prefix of some words from $L$, then $\xi \in L$.

I conjecture that for closed sets $L$, that if $L$ is regular and non-counting, then membership could be decided by comparing prefix and infixes, but I am stuck with the proof, so any hints or suggestions for me?

EDIT: There is a certain problem with the way it is stated, instead of locally testable use star-free, and instead of just presuppose a set to be closed I will presuppose it to be open or closed, so that the proposition is stable under complementation (which are the star-free and non-countable languages), see the comments.

$\endgroup$
  • 3
    $\begingroup$ Your claim about regular, noncounting languages is wrong. Let $L = \{ab\}$. Then $L$ is non counting (star-free). Let $u = ab$ and $v = aab$. Then $P_1(u) = P_1(v)$, $I_1(u) = I_1(v)$ and $S_1(u) = S_1(v)$. However $u \in L$ but $v \notin L$. $\endgroup$ – J.-E. Pin Nov 29 '13 at 18:20
  • $\begingroup$ thank you, it was ill-stated cause I did not connected the order of non-countability with the length of the common prefix, infixes and suffix. Had that in mind but wrote it wrongly. Your counter example is non-countable of order $n$ for every $n > 1$, and $P_2(u) \ne P_2(v)$ for your example, so this does not work any longer as a counter-example. $\endgroup$ – StefanH Nov 29 '13 at 22:22
  • 1
    $\begingroup$ Your claim is still wrong. Take $L = \{a,b,c\}^*ac^*$. This language is non-countable of order $1$ (its syntactic monoid is idempotent). Let $u = cbac$ and $v = cabc$. Then $P_1(u) = P_1(v)$, $I_1(u) = I_1(v)$ and $S_1(u) = S_1(v)$. However $u \in L$ but $v \notin L$. $\endgroup$ – J.-E. Pin Dec 1 '13 at 9:17
  • $\begingroup$ yes, you are confusing star-free languages and locally testable languages. $\endgroup$ – Denis Dec 2 '13 at 14:39
  • $\begingroup$ Putting aside the problem that your first claim is wrong, there is also the following problem with your conjecture: being locally testable, or aperiodic, is a property closed under complement. But your conjecture is about $L$ being closed. So it should be modified in either $L$ is clopen, or $L$ is either closed or open, so the conjecture is unchanged when we complement $L$. $\endgroup$ – Denis Dec 2 '13 at 14:43

Your Answer

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

Browse other questions tagged or ask your own question.