Introduction to semiring in Computer Science

Nattawat Piansakul
Sep 5, 2018 · 3 min read

From Nanyang Technological University ( 南洋理工大学) in Singapore lecture

By Lim Zhi Hao

semiring in computer science call tuple is a system

Tropical semiring is a system (ℝ ∪ {+∞},min{x,y},x+y,+∞,0)

Log semiring is a system (ℝ ∪ {-∞,∞},x(⊕log)y,x+y,+∞,0)

where x(⊕log)y = -log((e^-x)+(e^-y))

Boolean semiring is a system ({0,1},x or y,x and y,0,1)

Proability semiring is a system (ℝ+ ∪ {+∞},x+y,x*y,0,1)

from Minesutsu lab at University of Tokyo (東京大学)[ 東大] in Japan

by Josef R. Novak suggest that NLP and ASP application interrest in Tropical semiring and Log semiring

definition of semiring in Mathematics

semiring is ringoid is system (K, ⊕,⊗)

with condition for ringoid

1.K is a set

2.⊕ and ⊗ are binary operations on K

3. the operation ⊗ distributes over ⊕ both right and left.

∀a,b,c ∈ K : a⊗(b⊕c) = (a⊗b)⊕(a⊗c)…………left distribution

∀a,b,c ∈ K : (a⊕b)⊗c =(a⊗c)⊕(b⊗c)………….right distribution

which a⊗(b⊕c) we require that K is closed under ⊕.

and (a⊗b)⊕(a⊗c) we require that K is closed under ⊗. repectively

where ∀ b,c ∈ K×K : b⊕c ∈ K

∀ a,b ∈ K×K : a⊗b ∈ K and ∀ b,c ∈ K×K : b⊗c ∈ K

4. have Closure property

other refrence Closure definition
(K,*) be an algebraic structure.

Then K has the property of closure under * if and only if

: ∀x,y ∈ K×K : x*y ∈ K

K is said to be closed under *

or (K,*) is closed

a system (ℝ,+, ×) is distributive law in Algebra

and

with 2 condition with ringoid condition

1.(K,⊕) forms a semigroup

2.(K,⊕) forms a semigroup

A magma is an algebraic structure (K,*)such that K is closed under *.

That is, a magma definition

is a pair (K,*) where:

K is a set

* : K×K→K is a binary operation on K

semigroup have 2 axioms with (K,*)

  1. from magma ∀a,b ∈ K×K : a*b ∈ K (Closure)
  2. ∀a,b,c ∈ K : a*(b*c) = (a*b)*c ( Associativity)

semiring axioms

∀a,b ∈ K : a⊕b ∈ K

∀a,b,c ∈ K : a⊕(b⊕c) = (a⊕b)⊕c

∀a,b ∈ K : a⊗b ∈ K

∀a,b,c ∈ K : a⊗(b⊗c) = (a⊗b)⊗c

∀a,b,c ∈ K : a⊗(b⊕c) = (a⊗b)⊕(a⊗c)…………left distribution

∀a,b,c ∈ K : (a⊕b)⊗c =(a⊗c)⊕(b⊗c)………….right distribution

from Signal Processing on Databases Lincoln Laboratory at Massachusetts Institute of Technology in USA

can be use semiring in product formation in this way

In computer science it hard to explain with semiring with mathematical way.

Nattawat Piansakul

Written by

Mathematician Suankularb Wittayalai 128 (OSK128) interesting in Data mathematical analysis

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade