<p>The relation $pu^{k+1}q\in L\Rightarrow pu^k vu^kq\in L$ is true for any $p,q$, $k$ big enough and $v$ with $alph(v)\subseteq alph(u)$.</p>

<p>Let call $a$ the first letter of $u$ and $b$ the last letter.
Let $v$ with $alph(v)\subseteq alph(u)$, and $v'=uvu$.</p>

<p>Then by using the relation above with $v'$, we get that for any $p,q$ and $k$ big enough, we have $pu^{k}q\in L\Rightarrow pu^k vu^kq\in L$, which is the definition of $u^kvu^k\leq_L u^k$. In particular, for $n$ big enough, we get $u^{n!}vu^{n!}\leq_L u^{n!}$, which is the wanted equation.</p>

CC BY-SA 3.0
2014-01-09T10:42:18.720Z
"for $n$ big enough", $n$ is the size of the syntactic monoid and where it is guaranteed that it's size is big enough, maybe the size of it is smaller than the degree $k$.
StefanH
CC BY-SA 3.0
2014-01-09T13:40:32.527Z
the inequality is true for all $n$ larger than $k+1$, where $k$ is the degree of the language. So it suffices to take $n=\max\{k+1,|M|\}$, and you get what you want. Recall that $u^\pi=u^{n!}$ as soon as $n$ is at least $|M|$.
Denis
CC BY-SA 3.0
2014-01-09T00:41:02.177Z
2014-01-09T00:41:02.177Z
Denis
<p>A <em>polynomial language</em> is a languge which could be represented as the finite union of languages of the form:
$$
 A_0^* a_1 A_1^* a_2 \cdots a_k A_k^* \quad a_i \in X, A_i \subseteq X
$$
Such an expression is called a <em>monom</em> and it's <em>degree</em> is the value $k$.
Equivalently it could be defined as the smallest class containing the finite languages, languages of the form $A^*$ for $A \subseteq X$ and closed under union and concatentation.</p>

<p>The <em>degree</em> of a polynomial language is the maximum degree of the monoms in a minimal (with regard to the degree) representation of the polynomial language in the form of unions of monoms.</p>

<p>An <em>ordered monoid</em> $(M, \le)$ is a monoid $M$ together with a partial order which is compatible with multiplication. A set $D$ is called <em>downward closed</em> if $p \in D$ and $q \le p$ implies $q \in D$. An ordered monoid recognized a language $L$ via a morphism $\varphi : X^* \to M$ if
$$
 L = \varphi{-1}(\downarrow\varphi(L))
$$
where $\downarrow D$ denotes the smallest downward closed subset containing $D$.</p>

<p>For the syntactic monoid $Syn(L)$ there is a natural order given by $u \le_L v$ iff
$$
 \forall p,q \in X^* : pvq \in L \Rightarrow puq \in L.
$$
Then for $[u], [v] \in Syn(L)$ it is $[u] \le [v] :\Leftrightarrow u \le_L v$.</p>

<blockquote>
  <p>Let us consider a polynomial language $L$ of degree $k$ and words $u,v$ with $\mbox{alph}(v) \subseteq \mbox{alph}(u)$. Then for all $p,q$ we have $pu^{k+1} q \in L$ implies that $pu^kv u^k q\in L$, too. Thus, the syntactic orderd monoid of $L$ satisfied an equation of type $u^{\pi}vu^{\pi} \le_L u^{\pi}$ </p>
</blockquote>

<p>Remark: $u^{\pi}$ denotes the unique idempotent associated with $u$, for example $\pi = n!$ where $n$ is the size of the finite monoid.</p>

<p>The shaded paragraph I do not understand, the relation
$$
 pu^{k+1}q \in L \Rightarrow pu^k vu^k q \in L
$$
for $\mbox{alph}(v) \subseteq \mbox{alph}(u)$ and $k$ the degree of the polynomial is clear cause a monom of degree $k$ can "fix" just $k$ letters, and so some $u$ lies in some $A_i^* \subseteq X^*$ and so also $v$. But why does this order relation for the syntactic monoid follows? Is there any simple relation between the idempotent powers and the degree I do not see?</p>

<fl.formal-languages><automata-theory><algebra>
The polynomial languages and ordered syntactic monoids
StefanH
# The polynomial languages and ordered syntactic monoids

(Asked by: username_0 on 2014-01-08)

A *polynomial language* is a languge which could be represented as the finite union of languages of the form:
$$
A\_0^\* a\_1 A\_1^\* a\_2 \cdots a\_k A\_k^\* \quad a\_i \in X, A\_i \subseteq X
$$
Such an expression is called a *monom* and it's *degree* is the value $k$.
Equivalently it could be defined as the smallest class containing the finite languages, languages of the form $A^\*$ for $A \subseteq X$ and closed under union and concatentation.

The *degree* of a polynomial language is the maximum degree of the monoms in a minimal (with regard to the degree) representation of the polynomial language in the form of unions of monoms.

An *ordered monoid* $(M, \le)$ is a monoid $M$ together with a partial order which is compatible with multiplication. A set $D$ is called *downward closed* if $p \in D$ and $q \le p$ implies $q \in D$. An ordered monoid recognized a language $L$ via a morphism $\varphi : X^\* \to M$ if
$$
L = \varphi{-1}(\downarrow\varphi(L))
$$
where $\downarrow D$ denotes the smallest downward closed subset containing $D$.

For the syntactic monoid $Syn(L)$ there is a natural order given by $u \le\_L v$ iff
$$
\forall p,q \in X^\* : pvq \in L \Rightarrow puq \in L.
$$
Then for $[u], [v] \in Syn(L)$ it is $[u] \le [v] :\Leftrightarrow u \le\_L v$.

> Let us consider a polynomial language $L$ of degree $k$ and words $u,v$ with $\mbox{alph}(v) \subseteq \mbox{alph}(u)$. Then for all $p,q$ we have $pu^{k+1} q \in L$ implies that $pu^kv u^k q\in L$, too. Thus, the syntactic orderd monoid of $L$ satisfied an equation of type $u^{\pi}vu^{\pi} \le\_L u^{\pi}$

Remark: $u^{\pi}$ denotes the unique idempotent associated with $u$, for example $\pi = n!$ where $n$ is the size of the finite monoid.

The shaded paragraph I do not understand, the relation
$$
pu^{k+1}q \in L \Rightarrow pu^k vu^k q \in L
$$
for $\mbox{alph}(v) \subseteq \mbox{alph}(u)$ and $k$ the degree of the polynomial is clear cause a monom of degree $k$ can "fix" just $k$ letters, and so some $u$ lies in some $A\_i^\* \subseteq X^\*$ and so also $v$. But why does this order relation for the syntactic monoid follows? Is there any simple relation between the idempotent powers and the degree I do not see?

**Tags:** fl.formal-languages, automata-theory, algebra


---

## 1 answers

### Answer by username_1 on 2014-01-09. Score: 1 | Accepted answer

The relation $pu^{k+1}q\in L\Rightarrow pu^k vu^kq\in L$ is true for any $p,q$, $k$ big enough and $v$ with $alph(v)\subseteq alph(u)$.

Let call $a$ the first letter of $u$ and $b$ the last letter.
Let $v$ with $alph(v)\subseteq alph(u)$, and $v'=uvu$.

Then by using the relation above with $v'$, we get that for any $p,q$ and $k$ big enough, we have $pu^{k}q\in L\Rightarrow pu^k vu^kq\in L$, which is the definition of $u^kvu^k\leq\_L u^k$. In particular, for $n$ big enough, we get $u^{n!}vu^{n!}\leq\_L u^{n!}$, which is the wanted equation.

> **Comments:**
> **username_0**: "for $n$ big enough", $n$ is the size of the syntactic monoid and where it is guaranteed that it's size is big enough, maybe the size of it is smaller than the degree $k$.  
> **username_1**: the inequality is true for all $n$ larger than $k+1$, where $k$ is the degree of the language. So it suffices to take $n=\max\{k+1,|M|\}$, and you get what you want. Recall that $u^\pi=u^{n!}$ as soon as $n$ is at least $|M|$.  

---

