<p>There are plenty of semirings related to language theory. First of all, the Boolean semiring. Next any class of languages closed under finite union and (concatenation) product is a subsemiring of the semiring of all languages. For instance the rational (= regular) languages form a semiring. See also the related notion of <a href="http://en.wikipedia.org/wiki/Kleene_algebra" rel="noreferrer">Kleene algebra</a>.</p>

<p>The $k \times k$ matrices over a semiring do form a semiring. In particular, matrices over the Boolean semiring encode nondeterministic finite automata and matrices over the slightly larger semiring $\{-\infty, 0, 1\}$ encode transitions of a Büchi automaton. Matrices over a semiring are used to characterize <a href="http://tagh.de/tom/wp-content/uploads/berstelreutenauer2008.pdf" rel="noreferrer">rational series</a>.</p>

<p>The <a href="http://hal.archives-ouvertes.fr/hal-00113779/fr/" rel="noreferrer">tropical semirings</a>, in particular $(\mathbb{N} \cup \{+\infty\}, \min, +)$ and $(\mathbb{N} \cup \{-\infty\}, \max, +)$ play a proeminent role in automata theory. They also led to a new branch of mathematics, the <a href="http://en.wikipedia.org/wiki/Tropical_geometry" rel="noreferrer">tropical geometry</a>.</p>

CC BY-SA 3.0
2013-10-20T21:21:34.880Z
2013-10-20T21:21:34.880Z
J.-E. Pin
<p><a href="http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf" rel="nofollow">Fun with Semirings: A functional pearl on the abuse of linear algebra</a></p>

<p><a href="http://www.cse.chalmers.se/~bernardy/PP.pdf" rel="nofollow">Efficent Divide and Conquer parsing of context free languages</a> </p>

CC BY-SA 3.0
2013-10-21T20:08:46.837Z
2013-10-21T20:08:46.837Z
Chad Brewbaker
<p>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.</p>

<p>1 Given CNF grammar, the elements of semiring are sets of terminal and nonterminal symbols with the operations:</p>

<p>i) <em>Multiplication</em>, joining the two sets pair-wise according to CYK rule. For example given CNF grammar </p>

<pre><code>s: p p | q r
t: p q
u: q q
</code></pre>

<p>then</p>

<p>$ \{p,q,r\}\otimes \{p,r\} = \{s,t\} $ </p>

<p>ii) <em>Addition</em> is set union, e.g.</p>

<p>$ \{p,q\}\oplus \{q,r\} = \{p,q,r\} $</p>

<p>Unfortunately, multiplication is not associative.</p>

<p>2 The elements of second semiring are sets of not symbols but grammar rules [not necessarily in CNF] amended with position. The operations are</p>

<p>i) <em>Multiplication</em>, joining all matching pairs of elements according to Earley complete rule. For example given CNF grammar </p>

<pre><code>s: p q r 
r: s t | u
</code></pre>

<p>then</p>

<p>$ \{s: p \bullet q r,s: p q \bullet r\}\otimes \{r: u \bullet \} = \{s: p q r \bullet \} $ </p>

<p>ii) <em>Addition</em> is again the set union, e.g.</p>

<p>$ \{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\} $</p>

<p>This example is also deficient.  </p>

<p><a href="https://mathoverflow.net/questions/81370/substitution-semiring">Semiring with elements being sets of grammar rules and multiplication being rule substitution</a> 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.   </p>

<p>$ [t : s a] = \{ (t,sa),(ta,saa),(bt,bsa),(abt,absa),... \} $</p>

<p>Then, recognition of a word in a grammar is a chain of relational compositions, e.g.</p>

<p>$ [t:sa] \otimes [s:aa] \otimes \{(aaa,aaa)\} =  \{(t,aaa)\} $ </p>

<p>(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).</p>

<p>So, the question remains: is the <em>semiring of formal languages</em> over alphabet $\Sigma$ the only example?  </p>

CC BY-SA 3.0
2011-11-21T19:00:02.013Z
Doesn't this depend on what you mean by "specific to formal language theory"? Goodman's seminal "Semiring Parsing" has a slew of examples of semirings; surely the Boolean semiring is relevant to formal language theory, even if it's not specific to formal language theory.
Rob Simmons
CC BY-SA 3.0
2011-11-22T05:35:36.790Z
Yes it's subjective. Three examples above (two nonexamples:-) illustrate that the construction is expected to involve grammar rules or nonterminals, at least.
Tegiri Nenashi
CC BY-SA 3.0
2013-09-18T17:32:27.100Z
I am ready to answer the question raised in the title (there are indeed plenty of semirings occurring in formal language theory), but I am puzzled by your examples. It seems that you are looking for very specific examples. So, do you wish to have any example relevant to formal languages or specific ones occurring in parsing?
J.-E. Pin
CC BY-SA 3.0
2013-09-25T18:08:57.523Z
Yes, I had an expectation of semirings unique to formal language theory, and the above three examples demonstrate my failure to notice any. Still, please exhibit your examples: I'm eager to study semirings that I'm not familiar with.
Tegiri Nenashi
<fl.formal-languages>
Semiring examples from formal language theory
Tegiri Nenashi
# Semiring examples from formal language theory

(Asked by: username_0 on 2011-11-16)

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?

**Tags:** fl.formal-languages

> **Comments:**
> **username_1**: Doesn't this depend on what you mean by "specific to formal language theory"? Goodman's seminal "Semiring Parsing" has a slew of examples of semirings; surely the Boolean semiring is relevant to formal language theory, even if it's not specific to formal language theory.  
> **username_0**: Yes it's subjective. Three examples above (two nonexamples:-) illustrate that the construction is expected to involve grammar rules or nonterminals, at least.  
> **username_2**: I am ready to answer the question raised in the title (there are indeed plenty of semirings occurring in formal language theory), but I am puzzled by your examples. It seems that you are looking for very specific examples. So, do you wish to have any example relevant to formal languages or specific ones occurring in parsing?  
> **username_0**: Yes, I had an expectation of semirings unique to formal language theory, and the above three examples demonstrate my failure to notice any. Still, please exhibit your examples: I'm eager to study semirings that I'm not familiar with.  

---

## 2 answers

### Answer by username_2 on 2013-10-20. Score: 5

There are plenty of semirings related to language theory. First of all, the Boolean semiring. Next any class of languages closed under finite union and (concatenation) product is a subsemiring of the semiring of all languages. For instance the rational (= regular) languages form a semiring. See also the related notion of [Kleene algebra](http://en.wikipedia.org/wiki/Kleene_algebra).

The $k \times k$ matrices over a semiring do form a semiring. In particular, matrices over the Boolean semiring encode nondeterministic finite automata and matrices over the slightly larger semiring $\{-\infty, 0, 1\}$ encode transitions of a Büchi automaton. Matrices over a semiring are used to characterize [rational series](http://tagh.de/tom/wp-content/uploads/berstelreutenauer2008.pdf).

The [tropical semirings](http://hal.archives-ouvertes.fr/hal-00113779/fr/), in particular $(\mathbb{N} \cup \{+\infty\}, \min, +)$ and $(\mathbb{N} \cup \{-\infty\}, \max, +)$ play a proeminent role in automata theory. They also led to a new branch of mathematics, the [tropical geometry](http://en.wikipedia.org/wiki/Tropical_geometry).


---

### Answer by username_3 on 2013-10-21. Score: 1

[Fun with Semirings: A functional pearl on the abuse of linear algebra](http://www.cl.cam.ac.uk/~sd601/papers/semirings.pdf)

[Efficent Divide and Conquer parsing of context free languages](http://www.cse.chalmers.se/~bernardy/PP.pdf)


---

