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?


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.

  • $\begingroup$ "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$. $\endgroup$ – StefanH Jan 9 '14 at 10:42
  • 1
    $\begingroup$ 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|$. $\endgroup$ – Denis Jan 9 '14 at 13:40

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.