How to understand weight lexicographical orderings and degree lexicographical orderings?

281 Views Asked by At

Let $A=\{a_1,\ldots , a_n\}$.

(a) Let $w: {A^*}\rightarrow \mathbb{N}_{+}$ be a mapping that associates a positive integer with each letter. Define the $\mathbf{weight\ ordering} $ $\leq_{w}$ induced by $w$ as follows: \begin{align}\nonumber x\leq_{w}y\ \text{ if } \ w(x)\leq_{w}w(y). \end{align} Here $w$ is extended to a mapping from $A^*$ into $\mathbb{N}$ by taking $w(1):=0$ and $w(xa):=w(x)+w(a)$ for all $x\in A^*, a\in A$.

(b) The $\mathbf{lexicographical\ ordering}$ $\leq_{l}$ on $A^*$ is defined as following: $x\leq_{l}y$ if there is a non-empty element $z$ such that \begin{align}\nonumber x=yz\ \text{ or }\ x=ua_iv\ \text{ and }\ y=ua_jz \end{align} for some $u,v,z \in A^*$, and $i,j\in \{1,\ldots, n\}$ satisfying $i\leq j$.

The ordering $\leq_{wl}$ is called $\mathbf{weight\ lexicographical\ ordering}$ if it satisfies the condition $(a)$ and condition $(b)$.

Maybe we can define the $\mathbf{degree\ ordering} $ $\leq_{d}$ induced by $w$ as follows: \begin{align}\nonumber x\leq_{d}y\ \text{ if } \ \mathbf{deg}(x)\leq_{d}\mathbf{deg}(y). \end{align} Then the degree ordering is a weight ordering.

But I don't know whether the above definition of the degree ordering is corect?

1

There are 1 best solutions below

2
On BEST ANSWER

For a degree lexicographically order replace the weighted
quasiorder in the definition of the weighted lexicographically
order with the degree quasiorder, x <=_d y when deg(x) <= deg(y).