Seria racjonalna

W matematyce i informatyce szereg wymierny jest uogólnieniem koncepcji formalnych szeregów potęgowych nad pierścieniem do przypadku, gdy podstawowa struktura algebraiczna nie jest już pierścieniem, ale semiringiem i nie zakłada się, że sąsiednie nieokreślone są do siebie dodawane . Można je uważać za wyrażenia algebraiczne języka formalnego w skończonym alfabecie .

Definicja

Niech R będzie semiringiem , a A alfabetem skończonym.

Nieprzemienny wielomian nad A jest skończoną formalną sumą słów nad A . Tworzą półpierścień. ${\ displaystyle R \ langle A \ rangle}$ .

Szereg formalny to funkcja c o wartości R na wolnym monoidzie A ^* , którą można zapisać jako

{\ Displaystyle \ suma _ {w \ w A ^ {*}} c (w) w.}

Zbiór szeregów formalnych jest $oznaczony$ półpierścieniem

{\ Displaystyle c+d: w \ mapsto c (w) + d (w)}

{\ Displaystyle c \ cdot d: w \ mapsto \ suma _ {uv = w} c (u) \ cdot d (v)}

Nieprzemienny wielomian odpowiada zatem funkcji c na A ^* o skończonym nośniku .

W przypadku, gdy R jest pierścieniem, jest to pierścień Magnusa nad R .

Jeśli L jest językiem nad A , uważanym za podzbiór A ^* , możemy utworzyć szereg charakterystyczny L jako szereg formalny

{\ Displaystyle \ suma _ {w \ w L} w}

odpowiadający funkcji charakterystycznej L .

W ${\ displaystyle R \ langle \ langle A \ rangle \ rangle}$ można zdefiniować operację iteracji wyrażoną jako

{\ Displaystyle S ^ {*} = \ suma _ {n \ geq 0} S ^ {n}}

i sformalizowane jako

{\ Displaystyle c ^ {*} (w) = \ suma _ {u_ {1} u_ {2} \ cdots u_ {n} = w} c (u_ {1}) c (u_ {2}) \ cdots c (u_{n}).}

Operacje wymierne to dodawanie i mnożenie szeregów formalnych wraz z iteracją. Szereg wymierny to szereg formalny uzyskany w wyniku wymiernych operacji z ${\ Displaystyle R \ langle A \ rangle.}$

Zobacz też

Berstel, Jean ; Reutenauera, Christophe’a (2011). Nieprzemienne szeregi wymierne z zastosowaniami . Encyklopedia matematyki i jej zastosowań. Tom. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0 . Zbl 1250.68007 .

Dalsza lektura

Sakarowicz, Jacques (2009). Elementy teorii automatów . Przetłumaczone z francuskiego przez Reubena Thomasa. Cambridge: Cambridge University Press . Część IV (gdzie $seriami$ są one racjonalnymi). ISBN 978-0-521-84425-3 . Zbl 1188.68177 .
Droste, M. i Kuich, W. (2009). Semiringi i formalne serie mocy. Podręcznik automatów ważonych , 3–28. doi : 10.1007/978-3-642-01492-5_1
Sakarovitch, J. Seria racjonalnej i rozpoznawalnej władzy. Podręcznik automatów ważonych , 105–174 (2009). doi : 10.1007/978-3-642-01492-5_4
W.Kuich. Semiringi i formalne szeregi potęgowe: ich znaczenie dla języków formalnych i teorii automatów. W: G. Rozenberg i A. Salomaa, red., Handbook of Formal Languages, tom 1, rozdział 9, strony 609–677. Springera, Berlin, 1997