WFST中的代數(shù)半環(huán)

概覽

????????包括：半環(huán)定義挂滓、例行證明馒索、完備半環(huán)定義和解釋岖食；先把這幾個半環(huán)擺出來吧：

表1）剪切自Mohri weighted automata algorithms

? ? ? ? 為什么WFST要基于半環(huán)構(gòu)建呢红碑？我的理解是：一方面環(huán)這樣的代數(shù)結(jié)構(gòu)是比我們熟知的域（ $\mathbb {Q ,R, C, Q(\sqrt2)}$ ）更加普遍的、實用性更廣的結(jié)構(gòu)泡垃，可以讓W(xué)FST更加普適析珊。另一方面，WFST庫的設(shè)計只需考慮面向這些代數(shù)結(jié)構(gòu)編程蔑穴，只要WFST框架內(nèi)的運算模塊符和環(huán)的定義忠寻，無需考慮具體的任務(wù)相關(guān)知識；而使用者則需根據(jù)業(yè)務(wù)設(shè)計具體的適當(dāng)?shù)臋?quán)重環(huán)就能直接利用WFST框架存和，不同環(huán)對應(yīng)的功能奕剃；換句話說，這是個很棒的接口捐腿，例如kaldi中的代碼WeightType::Zero()纵朋，WeightType::One()就代表了環(huán)的加法中性元和乘法中性元。

我們先來簡單介紹一下基本的代數(shù)結(jié)構(gòu)：

環(huán)（ring）

設(shè) $R$ 是一個集合茄袖，其上定義了兩個二元運算操软，分別稱為“加法”和“乘法”，分別使用 $\oplus$ 和 $\otimes$ 作為記號宪祥，定義為 $\oplus : R \times R \to R$ 聂薪， $\otimes : R \times R \to R$ ，并且滿足下面的條件：

1） $R$ 關(guān)于 $\oplus, \otimes$ 運算封閉

2） $R$ 關(guān)于 $\oplus$ 運算構(gòu)成Abelian群

3） $R$ 關(guān)于 $\otimes$ 運算構(gòu)成幺半群

4）乘法運算 $\otimes$ 關(guān)于加法運算 $\oplus$ 滿足左分配律和右分配律

我們說 $(R, \oplus, \otimes,\overline{0},,\overline{1})$ 構(gòu)成了一個環(huán)品山，為了強調(diào)這里的0和1是抽象環(huán)的“加法中性元”和“乘法中性元”胆建，遵循Mohri的文章，我們特意使用上加bar來表示肘交，下面也稱”中性元“是”單位元“或”幺元“。

注：不同的書上對環(huán)的定義會有些許的不同扑馁，比如有人喜歡把上面條件（3）改為“ $R$ 關(guān)于 $\otimes$ 運算構(gòu)成半群semi-group“涯呻，而不是上面的幺半群monoid，這無非只是更傾向于是否把乘法中性元（即”幺“）放到乘法半群中去腻要；當(dāng)你需要環(huán)的性質(zhì)時复罐，你把它稱述清楚即可；這里我們還是遵循Mohri的定義雄家。

半環(huán)（semi-ring）

有了上面的環(huán)的定義效诅，那么什么叫半環(huán)呢？“半”的性質(zhì)肯定來自環(huán)的子結(jié)構(gòu)（即“群”），自然 $R$ 已經(jīng)關(guān)于 $\otimes$ 運算構(gòu)成半群乱投，那么“半環(huán)”的“半”字肯定就來自加法群了咽笼；即將上面“環(huán)”的定義做個剪裁：

1）、3）戚炫、4）保持不變剑刑；

2） $R$ 關(guān)于 $\otimes$ 構(gòu)成幺半群，當(dāng)然交換性依然滿足（即上面的abelian修飾詞）双肤，也就是不是所有的元素都有加法逆元了施掏。

顯然，半環(huán)比環(huán)的條件更加弱茅糜，因此更加普適七芭。

以下我們用五元組 $(S, \oplus, \otimes,\overline{0},,\overline{1})$ 來代表半環(huán)結(jié)構(gòu)，并且我們既使用 $S$ 來表示進行運算的元素所在集合蔑赘，也用 $S$ 表示這個半環(huán)的五元組定義抖苦。

簡單的形式證明

下面我們來證明一下上面表格（1）中的各個集合在對應(yīng)的運算下的確構(gòu)成半環(huán)，證明過程非常的形式化和簡單米死，我們權(quán)當(dāng)做個練習(xí)锌历。

Boolean Semiring

$S=(\{0,1\}, \vee, \wedge, 0, 1)$

verbose proof:

1） $0\oplus0 = 0 \vee0=0,\ 0\oplus1=0\vee1=1, \ 1\oplus0=1\vee0=1,\ 1\oplus 1=1\vee1 =1$ ，顯然關(guān)于加法封閉峦筒，而且“交換性”可以直接看出來究西，不過也可以由邏輯運算的交換性來保證∥锱纾“幺元”顯然就是0卤材，因為它與其它元素作加法運算，結(jié)果還是其它元素自己峦失；最后可以發(fā)現(xiàn)元素1的確不存在加法逆元扇丛。

2）加法結(jié)合率： $x\oplus(y\oplus z) = (x\oplus y)\oplus z$ ?顯然成立，因為只要 $x,y,z$ 中有一個是1尉辑，則兩邊均為1帆精；全為0的時候，兩邊顯然都是0隧魄。

3） $0\otimes0=0\wedge0=0,0\otimes1=0\wedge1=0,1\otimes0=1\wedge0=0,1\otimes1=1\wedge1=1$ 卓练，可見關(guān)于乘法運算封閉，存在乘法單位元 $\overline{1} = 1$ 购啄。

4）乘法結(jié)合律： $\oplus,\otimes$ 顯然成立襟企，因為只要 $x,y,z$ 中有一個為0，則兩邊全為0狮含；全為1的時候顽悼，兩邊都是1曼振。

5）分配律： $x\otimes(y\oplus z) = \begin{cases}1, x 和 y\oplus z 均為1 \\0,x和y\oplus z至少一個為0\end{cases}$

在case1中，當(dāng) $y\oplus z=1 \iff y=1\ \text {or} \ z=1$ 蔚龙，這意味著 $x\otimes y=1\ \text{or}\ x\otimes z=1$ 冰评，進而有 $(x\otimes y )\oplus (x\otimes z) =(x\otimes y )\vee(x\otimes z)= 1$ ，即此時分配律成立府蛇；

在case2中集索，若 $x=0$ ，則 $(x\otimes y )\oplus (x\otimes z) =0 \vee 0= 0$ 汇跨；若 $y \oplus z =0$ 务荆，則 $y=0\ \text{and} \ z=0$ ；顯然case2中分配律也成立穷遂；

由于這里的環(huán)是交換的函匕，所以我們沒有刻意強調(diào)左右分配律。

Probability Semiring

$S=({\mathbb R_{+}}\cup \{ +\infty\}, +, \times, 0,1)$

verbose proof:

1）由于這里的半環(huán)運算 $\oplus,\otimes$ 就是實數(shù)域中的加法和乘法運算蚪黑，因此由實數(shù)公理盅惜，可知 $\mathbb R_{+}$ 關(guān)于加法和乘法封閉；

2）再由無窮大運算相關(guān)性質(zhì)：

$\begin{aligned}a+(+\infty) &= +\infty \\ (+\infty)+(+\infty) &= +\infty \\a \cdot (+\infty) &= +\infty \\(+\infty)\cdot (+\infty) &= +\infty \end{aligned} ;\quad \forall a \in {\mathbb R}_{+}$

可知集合 ${\mathbb R_{+}}\cup \{ +\infty\}$ 的確關(guān)于加法和乘法封閉忌穿；

3）加法抒寂、乘法結(jié)合率，加法掠剑、乘法交換律屈芜，以及乘法關(guān)于加法的分配律都繼承自實數(shù)的運算律；

4）顯然加法幺元 $\overline 0_{S} = 0_{\mathbb R}$ 朴译，乘法幺元 $\overline 1_{S} = 1_{\mathbb R}$ 都存在井佑；

5）再次，除了0都不存在加法逆元眠寿，所以是半環(huán)躬翁。

Log Semiring

$S=({\mathbb R} \cup \{ -\infty,+\infty\}, \oplus_{\rm log}, +, +\infty,0)$ ，其中加法運算定義為： $x \oplus_{\rm log} y = -\log(e^{-x} + e^{-y})$

verbose proof:

1）顯然對于任意實數(shù) $x,y$ 盯拱，都有 $x \oplus_{\rm log} y$ 是一個實數(shù)盒发；下面考慮幾個特殊情況， $\forall y \in \mathbb R$ ：

$(+\infty) \oplus_{\rm log} y = -\log(e^{-\infty} + e^{-y}) = -\log(e^{-y}) =y$

$\begin{aligned}(-\infty) \oplus_{\rm log} y & = -\log(e^{\lim_{x\to+\infty}x} + e^{-y})\\& = -\lim_{x\to +\infty}\log(e^{x}(1+e^{-x-y})) \\&=-\lim_{x\to +\infty}(x + \log(1+e^{-x-y})) \\&= -\lim_{x\to +\infty} x \ - \log(1+\lim_{x\to \infty}e^{{-x-y}})\\&= -\infty -0 = -\infty\end{aligned}$

2）顯然坟乾，由于滿足交換性迹辐，我們只要驗證下面表格中的情況：

$\begin{array}{c|ccc}x & +\infty &+\infty & -\infty \\y & +\infty & -\infty & -\infty \\\hlinex\oplus y &+\infty &-\infty &-\infty\\\end{array}$

$(+\infty) \oplus_{\rm log} (+\infty) = -\log(e^{\lim_{x\to\infty}-x} + e^{\lim_{y\to\infty}-y}) = -\lim_{x,y\to \infty}\log(e^{-x}+e^{-y}) =- (-\infty )=+\infty$

$(+\infty) \oplus_{\rm log} (-\infty) = -\log(e^{\lim_{x\to+\infty}-x} + e^{\lim_{y\to-\infty}-y}) = -\lim_{x,y\to \infty}\log(e^{-x}+e^{y}) =- \lim_{y\to+\infty}\log e^{y}=-\infty$

$(-\infty) \oplus_{\rm log} (-\infty) = -\log(e^{\lim_{x\to +\infty}x} + e^{\lim_{y\to +\infty} y}) = -\lim_{x,y\to +\infty}\log(e^{x}+e^{y})$ ，令 $z = -\log(e^x+e^y)$ 甚侣，則 $e^z=\frac{1}{e^x+e^y}$ ，所以 $e^z \to 0 \ \text{as}\ x,y\to +\infty$ 间学，即 $z \to -\infty$

3）顯然殷费，通過觀察上面的（1）和（2）可以發(fā)現(xiàn) $+\infty$ 的確是“加法中性元”印荔；

4）由于Log-半環(huán)的乘法運算只是實數(shù)域的加法運算，顯然也滿足封閉性详羡、交換性仍律、結(jié)合性等等；

5）并且滿足 $(+\infty) \otimes x=(+\infty) + x = \infty$ , $(-\infty) \otimes x = (-\infty) + x = -\infty$ , $(+\infty)\otimes(+\infty)=(+\infty)+(+\infty)=(+\infty)$ , $(-\infty)\otimes(-\infty) = (-\infty)+(-\infty)=(-\infty)$ 实柠；

6）最后水泉，在拓展的實數(shù)域中 $(+\infty)\otimes(-\infty)=(+\infty)+(-\infty)$ 不是一個數(shù)，這樣的運算是無意義的窒盐；但是Mohri的文章中似乎沒提到這點草则，如果這條封閉性不滿足，那么嚴(yán)格意義上并不構(gòu)成半環(huán)蟹漓；不過是否可以參考積分學(xué)中的“主值意義下的積分”思路炕横，定義 $(+\infty)\otimes(-\infty)\equiv \lim_{x\to+\infty}x+\lim_{x\to-\infty}x=\lim_{x\to+\infty}(x - x)=\lim_{x\to+\infty}0 =0$ 呢？這樣就算封閉了葡粒；但是如果實際中份殿，并不會出現(xiàn)這樣的運算，那么這一點也是無關(guān)緊要的嗽交。

7）Log-半環(huán)的乘法運算關(guān)于加法運算的分配律卿嘲，也很好驗證，比如：

$\begin{aligned}x\otimes (y\oplus z)&\equiv x + (-\log(e^{-y}+e^{-z}))\\&=-\log e^{-x} -\log(e^{-y}+e^{-z})\\&=-\log e^{-x}(e^{-y}+e^{-z}) \\&=-\log e^{-(x+y)}+e^{-(x+z)} \\&\equiv (x\otimes y) \oplus (x\otimes z)\end{aligned}$

其中符號“ $\equiv$ ”是“by definition“的意思夫壁，并且 $x,y,z\in \mathbb R$ 拾枣；

顯然上式說明Log-半環(huán)的分配律在實數(shù)中成立，再來看看一些邊界case：

$+\infty\otimes (x\oplus y)=+\infty -\log(e^{-x}+e^{-y})=+\infty, \forall x,y\in \mathbb R$ 掌唾，另一方面 $(+\infty) \otimes x \oplus (+\infty) \otimes y=-\log(e^{-(+\infty+x)}+e^{-(\infty+y)}) =+\infty, \forall x,y\in \mathbb R$ 放前，所以分配律此時也成立；

$\begin{aligned}(+\infty)\otimes[(+\infty)\oplus (+\infty)] &= (+\infty) -\log(e^{-\infty}+e^{-\infty})\\&=(+\infty) +(+\infty)\\&=+\infty \in S\end{aligned}$

$\begin{aligned}(-\infty)\otimes[(-\infty)\oplus (-\infty)] &= (-\infty) -\log(e^{+\infty}+e^{+\infty})\\&=(-\infty) +(-\infty)\\&=-\infty \in S\end{aligned}$

但是這里出現(xiàn)一個例外情況： $(+\infty) \otimes [(+\infty) \oplus (-\infty)]$

$\begin{aligned}(+\infty)\otimes[(+\infty)\oplus(-\infty)]&=(+\infty) + (-\log(e^{-\infty}+e^{+\infty}))\\&=(+\infty) -\log e^{+\infty} \\&=(+\infty) +(-\infty)\\&=0\quad (\text {主值意義下})\end{aligned}$

而 $\begin{aligned}(+\infty)\otimes(+\infty)=+\infty, (+\infty) \otimes (-\infty)&= -\log(e^{-\infty}+e^{+\infty})=-\infty\\\end{aligned}$ 糯彬，因此有 $[(+\infty)\otimes(+\infty) ] \oplus [(+\infty)\otimes(-\infty)]=-\log(e^{-\infty} + e^{+\infty})=-\infty$ 凭语；我們發(fā)現(xiàn)此時若使用主值意義下的無窮大加法，則不滿足分配律撩扒！

所以似扔，前面的討論是欠考慮了（ok，這些隨筆都是我想到哪寫到哪搓谆，只要不是低級錯誤就不改了）炒辉；看來我們需要定義 $(+\infty)+(-\infty)=(-\infty)$ ，因為取主值是沒什么明顯道理的泉手；而讓運算滿足分配律則是明確的動機黔寇；不過回過頭來，以Log-半環(huán)的乘法運算視角來看斩萌，上面新的定義就是： $(+\infty)\otimes(-\infty)=-\infty$ 缝裤，這的確是相當(dāng)自然的（聯(lián)想一下實數(shù)域的平行case： $(+\infty)\cdot (-\infty) = -\infty$ ）屏轰。

8）Log-半環(huán)的乘法單位元顯然是0，顯然有 $0\otimes x = 0+x=x,\ \forall x \in \mathbb R\cup \{+\infty,-\infty\}$ 成立憋飞。

Tropical Semiring

$S=({\mathbb R}\cup \{ -\infty,+\infty\}, \min, +, +\infty,0)$

插曲

????????說到Tropical Semiring霎苗，這個名字很特別，我特意查了一下Tropical Semiring的含義：這個半環(huán)起初是由巴西的一個數(shù)學(xué)家提出來的榛做，而那些主導(dǎo)學(xué)術(shù)和技術(shù)的西方國家因為懶得去了解這位數(shù)學(xué)家唁盏，于是就憑著“巴西就是某個處于赤道上的國家”這一刻板印象，隨意地為這個半環(huán)取了這樣的一個名字检眯；在我看來厘擂，這真切地體現(xiàn)了西方國家一貫的傲慢形象。

????????說到這里轰传，我又想起來西方人起的另一個名字“中國余數(shù)定理”驴党，雖然（大概）所有的書上都是這么寫的，并且一些老師可能也是這么介紹的获茬，但我真的很反感這樣的名字港庄。不得不說，雖然我一直在吐槽“百度文庫”恕曲，但是這次它給這個定理用了中國人應(yīng)該用的名字“孫子定理”鹏氧。

proof:

1）顯然有 $\min(x,y) \in S ,\ \forall x,y \in\mathbb R\cup \{+\infty, -\infty\}$ 成立，因此關(guān)于半環(huán)加法封閉佩谣；

2）和Log-半環(huán)一樣把还， $x\otimes y = x+y \in S, \ \forall x,y \in S$ 成立，因此關(guān)于半環(huán)乘法也封閉茸俭；

3）結(jié)合率吊履、交換律仍然是繼承自實數(shù)域；

4）顯然有 $\min(+\infty, x) = x,\ \forall x \in S$ 成立调鬓，因此 $+\infty$ 的確是半環(huán)S的加法單位元艇炎；

5）顯然有 $0\otimes x = 0 + x = x, \ \forall x \in S$ 成立，因此0的確是半環(huán)S的乘法單位元腾窝；

6）最后驗證以下分配律缀踪，不妨設(shè) $y<z$ ，則 $x \otimes (y\oplus z) = x+\min(y, z)=x + y$ 虹脯，而 $(x\otimes y) \oplus (x\otimes z) =\min( x+y, x+z) =x+y$ 驴娃，所以分配律對 $x,y,z\in \mathbb R$ 成立；根據(jù)Log Semiring中的討論結(jié)果循集，亦可驗證這里當(dāng) $x,y,z \in \mathbb R \cup \{+\infty,-\infty\}$ 都成立唇敞。

半環(huán)的其它屬性

交換性（commutative）

注意，在環(huán)的定義中，并沒有要求乘法運算滿足交換性厚棵，例如一個矩陣環(huán)就是不交換的蕉世，當(dāng)一個半環(huán)的乘法運算滿足交換律的時候蔼紧，我們稱其為“交換半環(huán)”婆硬；顯然，有上面的討論奸例，可知上面的四個環(huán)均滿足交換性彬犯。

冪等性（idempotent）

若半環(huán)S滿足 $x\oplus x=x,\ \forall x \in S$ 都成立，則稱其滿足冪等性查吊；由 $1\vee1=1,0\vee0=0$ 可知Boolean Semiring是冪等的谐区；由 $x\oplus x = \min(x, x) = x,\ \forall x \in \mathbb R \cup \{-\infty, +\infty\}$ 成立可知Tropical Semiring也是冪等的。

完備半環(huán)（Complete Semiring）

設(shè) $(S, \oplus, \otimes, 0_R, 1_R)$ 為半環(huán)逻卖，設(shè) $I$ 為任意索引族（有限或無窮）宋列，和任意由 $S$ 中的元素構(gòu)成的集合 $\{a_i\}_{i\in I}$ ，都有 $S$ 關(guān)于累加運算 $\bigoplus_{i\in I}a_i$ 封閉评也；并且 $\bigoplus_{i\in I}a_i$ 的結(jié)果不依賴于求和運算中元素的順序炼杖；則我們稱其為“完備半環(huán)”，若還滿足下面幾個條件：

$\begin{aligned}&\bigoplus_{i\in I} a_i = 0_R \quad \quad \quad &\text{if}\ |I|=0\quad (2)\\&\bigoplus_{i\in I} a_i = a_i \quad \quad \quad &\text{if}\ |I|=1\quad (3)\\&\bigoplus_{i\in I} a_i = \bigoplus_{j\in J}\bigoplus_{i\in I_j}a_i \quad \quad \quad &\text{對}I\text{的任意一個不交并} I=\cup_j I_j\quad (4)\\&a \otimes ( \bigoplus_{i\in I} a_i) = \bigoplus_{i\in I} (a\otimes a_i )\quad \quad \quad &\forall a\in S \quad (5)\\&( \bigoplus_{i\in I} a_i)\otimes a = \bigoplus_{i\in I} (a_i \otimes a )\quad \quad \quad &\forall a\in S \quad (6)\\\end{aligned}$

星半環(huán)（Starsemiring）

在半環(huán) $(S, \oplus,\otimes, 0_R, 1_R)$ 上增加了星運算（即一元閉包運算） $\ast$ 盗迟，其定義為： $a^{\ast} = \bigoplus_{n=0}^{+\infty} a^n, \ \forall a \in S$ 坤邪，并且對無窮級數(shù)滿足結(jié)合率、交換律罚缕、分配律艇纺。

顯然一個完備半環(huán)是一個星半環(huán)，因為對于任意n邮弹，有 $a^{n} \in S$ 黔衡，再由完備半環(huán)關(guān)于無窮級數(shù)的封閉性，和性質(zhì)（5）（6）分配性即可得腌乡。

布爾半環(huán)是個完備半環(huán)盟劫，且 $0^{\ast} = \bigoplus_{n=0}^{+\infty} 0^n = 1\vee0\vee 0\vee\cdots = 1 \in \{0,1\}$ ， $1^{\ast} = \bigoplus_{n=0}^{+\infty} 1^n = 1\vee1\vee 1\vee\cdots = 1\in \{0,1\}$ 导饲；

熱帶半環(huán)也是一個完備半環(huán)捞高，且有：

$a^* = \begin{cases} 0 \quad & \text{若 }a \in \mathbb R_+\\-\infty \quad & \text{其它}\end{cases}$

以上兩個半環(huán)都是冪等半環(huán)，也有非冪等半環(huán)滿足完備性渣锦，例如概率半環(huán) $(\mathbb R_+\cup \{+\infty\}, +, \times, 0, 1)$ 硝岗，且有：

$a^* =\sum_{n=0}^{+\infty} a^n = \begin{cases}\frac{1}{1-a}\quad &\text{若} 0\leq a< 1;\\+\infty \quad & \text{若} a\geq1;\end{cases}$

? ? ? ? 我們已經(jīng)對WFST引入了半環(huán)結(jié)構(gòu)，使得在WFST上的相關(guān)運算是良定的袋毙；那么型檀，為什么還要引入“完備半環(huán)”和“星半環(huán)”的概念呢？

????????雖然在實際中WFST中只能處理有限個頂點听盖，和有限多個轉(zhuǎn)移弧胀溺，即有限的圖裂七；但是別忘了，我們在圖中會出現(xiàn)循環(huán)連接仓坞，比如：自循環(huán)（self-loop）背零，那么這樣就會出現(xiàn)無窮條路徑，而我們在WFST中經(jīng)常會遇到一族路徑的權(quán)重的累加運算无埃。

? ? ? ? 比如徙瓶，當(dāng)有限長度的路徑 $\pi$ 中出現(xiàn)一個自循環(huán)，則會出現(xiàn)可數(shù)無窮條路徑到達終點嫉称；當(dāng)出現(xiàn)兩個自循環(huán)時則會可數(shù)多個可數(shù)條路徑侦镇，再次仍是可數(shù)的，因此在圖中出現(xiàn)有限多個循環(huán)時织阅，總是可數(shù)無窮條路徑壳繁。

? ? ? ? 不管怎樣，我們的確需要考慮無窮的情況荔棉，即我們不僅需要半環(huán)對加法闹炉、乘法封閉，還需要對極限運算封閉江耀；因此我們需要引入完備性概念剩胁，確保我們在WSFT中的相關(guān)運算都是良定的。

參考：Mohri,?Weighted Automata Algorithms

最后編輯于：2022.11.28 17:34:25

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末祥国，一起剝皮案震驚了整個濱河市昵观，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌舌稀，老刑警劉巖啊犬，帶你破解...
沈念sama閱讀 222,252評論 6贊 516
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場離奇詭異壁查，居然都是意外死亡觉至，警方通過查閱死者的電腦和手機，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 94,886評論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門睡腿，熙熙樓的掌柜王于貴愁眉苦臉地迎上來语御，“玉大人，你說我怎么就攤上這事席怪∮Υ常” “怎么了？”我有些...
開封第一講書人閱讀 168,814評論 0贊 361
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵挂捻，是天一觀的道長碉纺。經(jīng)常有香客問我，道長，這世上最難降的妖魔是什么骨田？我笑而不...
開封第一講書人閱讀 59,869評論 1贊 299
?港島之戀（遺憾婚禮）
正文為了忘掉前任耿导，我火速辦了婚禮，結(jié)果婚禮上态贤，老公的妹妹穿的比我還像新娘舱呻。我一直安慰自己，他們只是感情好抵卫，可當(dāng)我...
茶點故事閱讀 68,888評論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布狮荔。她就那樣靜靜地躺著，像睡著了一般介粘。火紅的嫁衣襯著肌膚如雪。梳的紋絲不亂的頭發(fā)上晚树，一...
開封第一講書人閱讀 52,475評論 1贊 312
城市分裂傳說
那天姻采，我揣著相機與錄音，去河邊找鬼爵憎。笑死慨亲，一個胖子當(dāng)著我的面吹牛，可吹牛的內(nèi)容都是我干的宝鼓。我是一名探鬼主播刑棵，決...
沈念sama閱讀 41,010評論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場噩夢啊……” “哼愚铡！你這毒婦竟也來了蛉签？” 一聲冷哼從身側(cè)響起，我...
開封第一講書人閱讀 39,924評論 0贊 277
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤沥寥，失蹤者是張志新（化名）和其女友劉穎碍舍，沒想到半個月后，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體邑雅，經(jīng)...
沈念sama閱讀 46,469評論 1贊 319
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡片橡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 38,552評論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年，在試婚紗的時候發(fā)現(xiàn)自己被綠了淮野。大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片捧书。...
茶點故事閱讀 40,680評論 1贊 353
活死人
序言：一個原本活蹦亂跳的男人離奇死亡，死狀恐怖骤星，靈堂內(nèi)的尸體忽然破棺而出经瓷，到底是詐尸還是另有隱情，我是刑警寧澤妈踊，帶...
沈念sama閱讀 36,362評論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布了嚎，位于F島的核電站，受9級特大地震影響，放射性物質(zhì)發(fā)生泄漏歪泳。R本人自食惡果不足惜萝勤，卻給世界環(huán)境...
茶點故事閱讀 42,037評論 3贊 335
男人毒藥：我在死后第九天來索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望呐伞。院中可真熱鬧敌卓，春花似錦、人聲如沸伶氢。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,519評論 0贊 25
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽癣防。三九已至蜗巧，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間蕾盯，已是汗流浹背幕屹。一陣腳步聲響...
開封第一講書人閱讀 33,621評論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留级遭，地道東北人望拖。一個月前我還...
沈念sama閱讀 49,099評論 3贊 378
代替公主和親
正文我出身青樓，卻偏偏與公主長得像挫鸽，于是被迫代替她去往敵國和親说敏。傳聞我的和親對象是個殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點故事閱讀 45,691評論 2贊 361

WFST中的代數(shù)半環(huán)

概覽

環(huán)（ring）

半環(huán)（semi-ring）

簡單的形式證明

Boolean Semiring

Probability Semiring

Log Semiring

Tropical Semiring

半環(huán)的其它屬性

完備半環(huán)（Complete Semiring）

星半環(huán)（Starsemiring）

推薦閱讀更多精彩內(nèi)容