<p>A language $L \subseteq X^*$ is non-counting of order $n &gt; 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 &gt; 0 $ iff for all $u,v \in X^*, \eta \in X^{\omega}$
$$
 uv^{n}\eta \in L \Leftrightarrow uv^{n+1} \eta \in L.
$$</p>

<p>When talking about languages over finite words, i.e. subsets $L$ of $X^*$ every regular, noncounting languages of order $n &gt; 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 &gt; 0$ then they are either both in $L$ or both not in $L$.</p>

<p>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 &gt; 0$. Fix some $n &gt; 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$.</p>

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

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

<p><strong>EDIT</strong>: 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.</p>

CC BY-SA 3.0
2013-11-29T18:20:44.583Z
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$.
J.-E. Pin
CC BY-SA 3.0
2013-11-29T22:22:26.783Z
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.
StefanH
CC BY-SA 3.0
2013-12-01T09:17:04.630Z
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$.
J.-E. Pin
CC BY-SA 3.0
2013-12-02T14:39:21.483Z
yes, you are confusing star-free languages and locally testable languages.
Denis
CC BY-SA 3.0
2013-12-02T14:43:43.750Z
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$.
Denis
CC BY-SA 3.0
2013-12-06T23:10:25.783Z
J.E.Pin: Yes, your example shows me I confused star-free and locally testable, locally testable languages could not handle a notion of order like in your example where after an a it is not allowed that another a or b occurs. So I confused the notion of star-free and locally testable, the locally testable languages are properly contained in the class of star-free languages.
StefanH
CC BY-SA 3.0
2013-12-06T23:11:26.070Z
@dkuper Yes your objection is another problem, even if I change my conjecture to star-free instead of locally testable. For clopen sets: the clopen sets in Cantor space are of the form $W\cdot X^{\omega}$ with $W$ finite, and so are non-counting of order $n := \max\{ |w| : w \in W \}$ and of course star-free. But that is not very enlightning.
StefanH
CC BY-SA 3.0
2013-12-06T23:12:30.827Z
The open sets in Cantor space are of the form $W X^{\omega}$ with $W \subseteq X^*$ arbitrary, so in general they are not star-free or non-couting, but if these properties are equal if we had a set which is closed or open is still an interesing question. My goal is to transfer properties from the finite to the infinite, and I guess that topology might help me, in particular the Borel hierarchy. At best I get theorems like $P(L)$ is equivalent to  $S(L)$ iff $L$ is in a certain Borel class.
StefanH
<fl.formal-languages><automata-theory><regular-language><topology>
Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space
StefanH
# Transfering properties from subsets of $X^*$ to subsets of $X^{\omega}$ by using the topology induces by Cantor space

(Asked by: username_0 on 2013-11-29)

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.

**Tags:** fl.formal-languages, automata-theory, regular-language, topology

> **Comments:**
> **username_1**: 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$.  
> **username_0**: 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.  
> **username_1**: 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$.  
> **username_2**: yes, you are confusing star-free languages and locally testable languages.  
> **username_2**: 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$.  
> **username_0**: J.E.Pin: Yes, your example shows me I confused star-free and locally testable, locally testable languages could not handle a notion of order like in your example where after an a it is not allowed that another a or b occurs. So I confused the notion of star-free and locally testable, the locally testable languages are properly contained in the class of star-free languages.  
> **username_0**: @dkuper Yes your objection is another problem, even if I change my conjecture to star-free instead of locally testable. For clopen sets: the clopen sets in Cantor space are of the form $W\cdot X^{\omega}$ with $W$ finite, and so are non-counting of order $n := \max\{ |w| : w \in W \}$ and of course star-free. But that is not very enlightning.  
> **username_0**: The open sets in Cantor space are of the form $W X^{\omega}$ with $W \subseteq X^*$ arbitrary, so in general they are not star-free or non-couting, but if these properties are equal if we had a set which is closed or open is still an interesing question. My goal is to transfer properties from the finite to the infinite, and I guess that topology might help me, in particular the Borel hierarchy. At best I get theorems like $P(L)$ is equivalent to  $S(L)$ iff $L$ is in a certain Borel class.  

---

## 0 answers

