Editing Formal power series (section)

=== On a semiring ===
{{expand section|sum, product, examples|date=August 2014}}

Given an [[Alphabet (formal languages)|alphabet]] <math>\Sigma</math> and a [[semiring]] <math>S</math>. The formal power series over <math>S</math> supported on the language <math>\Sigma^*</math> is denoted by <math>S\langle\langle \Sigma^*\rangle\rangle</math>. It consists of all mappings <math>r:\Sigma^*\to S</math>, where <math>\Sigma^*</math> is the [[free monoid]] generated by the non-empty set <math>\Sigma</math>.

The elements of <math>S\langle\langle \Sigma^*\rangle\rangle</math> can be written as formal sums

:<math>r = \sum_{w \in \Sigma^*} (r,w)w.</math>

where <math>(r,w)</math> denotes the value of <math>r</math> at the word <math>w\in\Sigma^*</math>. The elements <math>(r,w)\in S</math> are called the coefficients of <math>r</math>.

For <math>r\in S\langle\langle \Sigma^*\rangle\rangle</math> the support of <math>r</math> is the set

:<math>\operatorname{supp}(r)=\{w\in\Sigma^*|\ (r,w)\neq 0\}</math>

A series where every coefficient is either <math>0</math> or <math>1</math> is called the characteristic series of its support.

The subset of <math>S\langle\langle \Sigma^*\rangle\rangle</math> consisting of all series with a finite support is denoted by <math>S\langle \Sigma^*\rangle</math> and called polynomials.

For <math>r_1, r_2\in S\langle\langle \Sigma^*\rangle\rangle</math> and <math>s\in S</math>, the sum <math>r_1+r_2</math> is defined by 
:<math>(r_1+r_2,w)=(r_1,w)+(r_2,w)</math>
The (Cauchy) product <math>r_1\cdot r_2</math> is defined by
:<math>(r_1\cdot r_2,w) = \sum_{w_1w_2=w}(r_1,w_1)(r_2,w_2)</math>
The Hadamard product <math>r_1\odot r_2</math> is defined by
:<math>(r_1\odot r_2,w)=(r_1,w)(r_2,w)</math>
And the products by a scalar <math>sr_1</math> and <math>r_1s</math> by
:<math>(sr_1,w)=s(r_1,w)</math> and <math>(r_1s,w)=(r_1,w)s</math>, respectively.

With these operations <math>(S\langle\langle \Sigma^*\rangle\rangle,+,\cdot,0,\varepsilon)</math> and <math>(S\langle \Sigma^*\rangle, +,\cdot,0,\varepsilon)</math> are semirings, where <math>\varepsilon</math> is the empty word in <math>\Sigma^*</math>.

These formal power series are used to model the behavior of [[weighted automata]], in [[theoretical computer science]], when the coefficients <math>(r,w)</math> of the series are taken to be the weight of a path with label <math>w</math> in the automata.<!-- the correct symbols for the double angled braces are ⟪ and ⟫; but they work poorly in many browsers. Wikipedia's TeX doesn't support \llangle and \rrangle. Also no support for Greek italics in wiki TeX it seems --><ref>Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. ''Handbook of Weighted Automata'', 3–28. {{doi|10.1007/978-3-642-01492-5_1}}, p. 12</ref>