Serie racional

En matemáticas e informática , una serie racional es una generalización del concepto de serie de potencias formales sobre un anillo para el caso en que la estructura algebraica básica ya no es un anillo sino un semianillo , y no se supone que las indeterminadas adjuntas conmuten . Pueden considerarse como expresiones algebraicas de un lenguaje formal sobre un alfabeto finito .

Definición

Sea R un semianillo y A un alfabeto finito.

Un polinomio no conmutativo sobre A es una suma formal finita de palabras sobre A . Forman un semianillo . ${\displaystyle R\langle A\rangle }$

Una serie formal es una función c de valor R , en el monoide libre A ^* , que puede escribirse como

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

El conjunto de series formales se denota y se convierte en un semianillo bajo las operaciones ${\displaystyle R\langle \langle A\rangle \rangle }$

${\displaystyle c+d:w\mapsto c(w)+d(w)}$

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

Un polinomio no conmutativo corresponde entonces a una función c en A ^{* de} soporte finito .

En el caso en que R sea un anillo, entonces este es el anillo Magnus sobre R. ^[1 ]

Si L es un lenguaje sobre A , considerado como un subconjunto de A ^* podemos formar la serie característica de L como la serie formal

${\displaystyle \sum _{w\in L}w}$

correspondiente a la función característica de L .

En uno se puede definir una operación de iteración expresada como ${\displaystyle R\langle \langle A\rangle \rangle }$

${\displaystyle S^{*}=\sum _{n\geq 0}S^{n}}$

y formalizado como

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

Las operaciones racionales son la suma y multiplicación de series formales, junto con la iteración. Una serie racional es una serie formal obtenida por operaciones racionales a partir de ${\displaystyle R\langle A\rangle .}$

Véase también

• Serie de potencias formales
• Lenguaje racional
• Conjunto racional
• Serie de Hahn (serie de Malcev-Neumann)
• Autómata ponderado

Referencias

1. Koch, Helmut (1997). Teoría algebraica de números . Encycl. Math. Sci. Vol. 62 (segunda edición de la primera edición). Springer-Verlag . pág. 167. ISBN. 3-540-63003-1.Zbl 0819.11044  .

• Berstel, Jean ; Reutenauer, Christophe (2011). Series racionales no conmutativas con aplicaciones . Enciclopedia de matemáticas y sus aplicaciones. Vol. 137. Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0.Zbl 1250.68007  .

Lectura adicional

• Sakarovitch, Jacques (2009). Elementos de la teoría de autómatas . Traducido del francés por Reuben Thomas. Cambridge: Cambridge University Press . Parte IV (donde se denominan series racionales). ISBN ${\displaystyle \mathbb {K} }$ 978-0-521-84425-3.Zbl 1188.68177  .
• Droste, M. y Kuich, W. (2009). Semirings and Formal Power Series. Manual de autómatas ponderados , 3–28. doi :10.1007/978-3-642-01492-5_1
• Sakarovitch, J. Series de potencias racionales y reconocibles. Manual de autómatas ponderados , 105–174 (2009). doi :10.1007/978-3-642-01492-5_4
• W. Kuich. Semirings and formal power series : Their importance to formal language and automata theory (Semirings and formal power series: Su relevancia para los lenguajes formales y la teoría de autómatas). En G. Rozenberg y A. Salomaa, editores, Handbook of Formal Languages, volumen 1, capítulo 9, páginas 609–677. Springer, Berlín, 1997.