Rationell serie

Inom matematik och datavetenskap är en rationell serie en generalisering av begreppet formell potensserie över en ring till fallet när den grundläggande algebraiska strukturen inte längre är en ring utan en semiring , och de obestämda angränsande inte antas pendla . De kan betraktas som algebraiska uttryck för ett formellt språk över ett ändligt alfabet .

Definition

Låt R vara ett semiring och A ett ändligt alfabet.

Ett icke-kommutativt polynom över A är en finit formell summa av ord över A . De bildar en semiring $R\langle A\rangle$ .

En formell serie är en R -värd funktion c , på den fria monoiden A ^* , som kan skrivas som

\sum _{w\in A^{*}}c(w)w.

Uppsättningen av formella serier betecknas $R\langle \langle A\rangle \rangle$ och blir en semiring under operationerna

c+d:w\mapsto c(w)+d(w)

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

Ett icke-kommutativt polynom motsvarar alltså en funktion c på A ^* av finit stöd .

I det fall då R är en ring, så är detta Magnus-ringen över R .

Om L är ett språk över A , betraktat som en delmängd av A ^* kan vi bilda den karakteristiska serien av L som den formella serien

\sum _{w\in L}w

motsvarande den karakteristiska funktionen för L .

I $R\langle \langle A\rangle \rangle$ kan man definiera en iterationsoperation uttryckt som

S^{*}=\summa _{n\geq 0}S^{n}

och formaliserad som

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

De rationella operationerna är addition och multiplikation av formella serier, tillsammans med iteration. En rationell serie är en formell serie som erhålls genom rationella operationer från $R\langle A\rangle .$

Se även

Berstel, Jean ; Reutenauer, Christophe (2011). Icke-kommutativa rationella serier med tillämpningar . Encyclopedia of Mathematics och dess tillämpningar. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0 . Zbl 1250.68007 .

Vidare läsning

Sakarovitch, Jacques (2009). Element i automatteorin . Översatt från franskan av Reuben Thomas. Cambridge: Cambridge University Press . Del IV (där de kallas $\mathbb {K}$ -rationella serier). ISBN 978-0-521-84425-3 . Zbl 1188.68177 .
Droste, M., & Kuich, W. (2009). Semirings och Formal Power Series. Handbook of Weighted Automata , 3–28. doi : 10.1007/978-3-642-01492-5_1
Sakarovitch, J. Rational and Recognizable Power Series. Handbook of Weighted Automata , 105–174 (2009). doi : 10.1007/978-3-642-01492-5_4
W. Kuich. Semirings och formella kraftserier: Deras relevans för formella språk och automatteori. I G. Rozenberg och A. Salomaa, redaktörer, Handbok i formella språk, volym 1, kapitel 9, sidorna 609–677. Springer, Berlin, 1997