Série rationnelle - Rational series

En mathématiques et en informatique, une série rationnelle est une généralisation du concept de série de puissances formelles sur un anneau au cas où la structure algébrique de base n'est plus un anneau mais un semirage , et les indéterminés adjacents ne sont pas supposés commuer . Ils peuvent être considérés comme des expressions algébriques d'un langage formel sur un alphabet fini .

Définition

Soit R un semi - intervalle et A un alphabet fini.

Un polynôme non commutatif sur A est une somme formelle finie de mots sur A . Ils forment un semirage . ${\ displaystyle R \ langle A \ rangle}$

Une série formelle est une fonction R- évaluée c , sur le monoïde libre A ^* , qui peut s'écrire

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

L'ensemble des séries formelles est noté et devient un semirage sous les opérations ${\ 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 polynôme non commutatif correspond donc à une fonction c sur A ^* de support fini.

Dans le cas où R est un cycle, alors c'est l' anneau Magnus sur R .

Si L est un langage sur A , considéré comme un sous-ensemble de A ^* on peut former la série caractéristique de L comme la série formelle

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

correspondant à la fonction caractéristique de L .

Dans on peut définir une opération d' itération exprimée comme ${\ displaystyle R \ langle \ langle A \ rangle \ rangle}$

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

et formalisé comme

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

Les opérations rationnelles sont l'addition et la multiplication de séries formelles, ainsi que l'itération. Une série rationnelle est une série formelle obtenue par des opérations rationnelles à partir de . ${\ displaystyle R \ langle A \ rangle}$

Voir également

• Série de puissance formelle
• Langage rationnel
• Ensemble rationnel
• Série Hahn ( série Malcev – Neumann)
• Automate pondéré

Les références

• Berstel, Jean ; Reutenauer, Christophe (2011). Série rationnelle non commutative avec applications . Encyclopédie des mathématiques et de ses applications. 137 . Cambridge: Cambridge University Press . ISBN 978-0-521-19022-0. Zbl  1250.68007 .

Lectures complémentaires

• Sakarovitch, Jacques (2009). Éléments de la théorie des automates . Traduit du français par Reuben Thomas. Cambridge: Cambridge University Press . Partie IV (où ils sont appelés -séries rationnelles). ISBN${\ displaystyle \ mathbb {K}}$ 978-0-521-84425-3. Zbl  1188.68177 .
• Droste, M. et Kuich, W. (2009). Semirings et série Power formelle. Manuel des automates pondérés , 3–28. doi : 10.1007 / 978-3-642-01492-5_1
• Sakarovitch, J. Série de puissance rationnelle et reconnaissable. Manuel des automates pondérés , 105–174 (2009). doi : 10.1007 / 978-3-642-01492-5_4
• W. Kuich. Sémirings et séries de puissance formelles: leur pertinence pour les langages formels et la théorie des automates. Dans G. Rozenberg et A. Salomaa, éditeurs, Handbook of Formal Languages, volume 1, chapitre 9, pages 609–677. Springer, Berlin, 1997

Cet article lié à l' algèbre est un bout . Vous pouvez aider Wikipedia en le développant . v t e