Wortersetzungssystem R über ,
Bsp:
R = {aaaba} über
= {a, b}
Matrix-Interpretation (Halbring D, Dimension n)
[ . ] : Dn×n
für Buchstaben
für Wörter durch Multiplikation: [x1,..., xk] = [x1]o...o[xk]
zulässig:
x
: [x]1, 1
0D
kompatibel:
(l, r)
R :
i, j : [l]i, j > 0[r]i, j
wobei
p > 0q(p = 0D = q)
(p > q)
Beispiel:
D = (
{ +
}, min, max),
[a] = ,[b] =
.