I'm learning algebraic theory of parsing. My first problem is identifying semiring examples which are specific to formal language theory. Here is an attempt to construct two examples.
1 Given CNF grammar, the elements of semiring are sets of terminal and nonterminal symbols with the operations:
i) Multiplication, joining the two sets pair-wise according to CYK rule. For example given CNF grammar
s: p p | q r
t: p q
u: q q
then
$ \{p,q,r\}\otimes \{p,r\} = \{s,t\} $
ii) Addition is set union, e.g.
$ \{p,q\}\oplus \{q,r\} = \{p,q,r\} $
Unfortunately, multiplication is not associative.
2 The elements of second semiring are sets of not symbols but grammar rules [not necessarily in CNF] amended with position. The operations are
i) Multiplication, joining all matching pairs of elements according to Earley complete rule. For example given CNF grammar
s: p q r
r: s t | u
then
$ \{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \} $
ii) Addition is again the set union, e.g.
$ \{s: p \bullet q r, r: \bullet s t\}\oplus \{r: u \bullet \} = \{s: p \bullet q r, r: \bullet s t, r: u \bullet\} $
This example is also deficient.
Semiring with elements being sets of grammar rules and multiplication being rule substitution seems to work fine. Yet, this is just relation algebra in disguise. Indeed, let view each grammar rule as an equivalence class -- a set of pairs of words consisting terminal and nonterminal letters related by rule's application, e.g.
$ [t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \} $
Then, recognition of a word in a grammar is a chain of relational compositions, e.g.
$ [t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} = \{(t,aaa)\} $
(This monomial is reminiscent of semiring parser polynomial from Josh Goodman PhD thesis; however, let reiterate that constructing new semirings by taking polynomials and matrices is not of our interest here).
So, the question remains: is the semiring of formal languages over alphabet $\Sigma$ the only example?