Rationality, irrationality, and Wilf equivalence in generalized factor order

NEW

Problem: Reconstructed statement: for ordinary factor order on words over a finite alphabet $\Sigma$, and fixed $u\in\Sigma^*$, is

always context-free? This is the natural reading because the paper introduces $\mathcal M(u)$ in the ordinary factor-order section and then asks whether the non-regular examples might still be CFGs. A narrower possible reading is the particular binary example $\mathcal M(a)$; the result below resolves the general question negatively.

Result: No. There is a finite alphabet and a fixed word $u$ for which $\mathcal M(u)$ is not context-free.

Let

as an antichain, so factor order is ordinary substring order, and take $u=\mathtt a$. For $x\in\{\mathtt0,\mathtt1\}^*$, put

By Björner’s formula for the Möbius function of ordinary factor order: if $|w|-|u|>2$, then $\mu(u,w)\ne0$ only in the case $u\le o(w)\not\le i(w)$, and then $\mu(u,w)=\mu(u,o(w))$, where $o(w)$ is the longest proper border and $i(w)$ is $w$ with first and last letters deleted.

First, $o(p_x)=\mathtt a$, and $i(p_x)=\mathtt\ell x\mathtt r$ contains no $\mathtt a$. Hence

Now consider $W_{x,y}$. Any border of $W_{x,y}$ of length $>1$ must start with $\mathtt a\mathtt\ell$. The only proper suffix position beginning with $\mathtt a\mathtt\ell$ is the start of the final $p_y$. Thus such a border exists iff $p_y$ is also the corresponding prefix, which happens iff $x=y$. Therefore

If $x=y$, then $p_x$ occurs in $W_{x,x}$ only as prefix and suffix, so $p_x\not\le i(W_{x,x})$, and therefore

If $x\ne y$, then $o(W_{x,y})=\mathtt a$, but $\mathtt a\le i(W_{x,y})$, so Björner’s first case fails and all other cases are excluded by length. Hence $\mu(\mathtt a,W_{x,y})=0$.

Let

a regular language. Then

If $\mathcal M(\mathtt a)$ were context-free, this intersection would be context-free. Applying the homomorphism erasing $\mathtt a,\mathtt\ell,\mathtt r$, fixing $\mathtt0,\mathtt1$, and sending $\mathtt d\mapsto \#$, we would get

the standard copy language, which is not context-free by the CFL pumping lemma. Contradiction.

Thus $\mathcal M(u)$ is not always context-free.

Citation: Uses Björner, “The Möbius function of factor order,” Theoret. Comput. Sci. 117 (1993), 91–98. Standard closure properties and pumping lemma: Hopcroft–Ullman, Introduction to Automata Theory, Languages, and Computation, 1979.