Ordnungsconstraints für Matrizen

Wortersetzungssystem R über $\Sigma$,

Bsp: R = {aa$\to$aba} über $\Sigma$ = {a, b}

Matrix-Interpretation (Halbring D, Dimension n)

[ ^. ] : $\Sigma$$\to$D^n×n für Buchstaben

für Wörter durch Multiplikation: [x₁,..., x_k] = [x₁]o...o[x_k]

zulässig: $\forall$x $\in$ $\Sigma$ : [x]_{1, 1} $\neq$ 0_D

kompatibel: $\forall$(l, r) $\in$ R : $\forall$i, j : [l]_{i, j} > ₀[r]_{i, j}

wobei p > ₀q$\iff$(p = 0_D = q) $\vee$ (p > q)

Beispiel: D = ($\mathbb {N}$ $\cup$ { + $\infty$}, min, max),

[a] = $\left(\vphantom{\begin{array}{ccc} 2 & +\infty & 0 \\ 1 & +\infty & 0 \\ +\infty & +\infty & +\infty \end{array}}\right.$$\begin{array}{ccc} 2 & +\infty & 0 \\ 1 & +\infty & 0 \\ +\infty & +\infty & +\infty \end{array}$$\left.\vphantom{\begin{array}{ccc} 2 & +\infty & 0 \\ 1 & +\infty & 0 \\ +\infty & +\infty & +\infty \end{array}}\right)$,[b] = $\left(\vphantom{\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}}\right.$$\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}$$\left.\vphantom{\begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{array}}\right)$.