Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have the following statement in a paper:

Let $\Psi$ be the formal power series defined over the alphabet $\Omega$ and the log semiring by: $(\Psi, (a, b)) = -log(c((a,b)))$ for $(a,b) \in \Omega$, and let $S$ be the formal pwer series $S$ over the log semiring defined by: $S=\Omega^*+\Psi+\Omega^*$ (an alphabet is a finite set of symbols and $\Omega$ contains pairs of such symbols.)

It continues: $S$ is a rational power series as a +-product and closure of the polynomial power series $\Omega$ and $\Psi$.

What exactly is meant here? I know about the automata theoretical aspects, but I haven't heard of the notion "formal power series" over an alphabet and a semiring. How can I think of this?

The paper is at http://www.cs.nyu.edu/~mohri/pub/ , [93] and [99] (virtually identical), page 15 and page 17 in the 22-page paper. It is a verbatim copy.

share|improve this question
1  
Is that a verbatim copy from the paper? –  Mariano Suárez-Alvarez Jan 24 '11 at 5:02
    
Could you provide a link or a precise reference to the paper, please? –  t.b. Jan 24 '11 at 5:04
    
yes. updated. thanks. –  Felix Dombek Jan 24 '11 at 5:17
    
Also, there might be typos in the paper. I don't understand why $\Omega$ should suddenly be a formal power series when it was a finite set of symbols before. –  Felix Dombek Jan 24 '11 at 5:19
    
and why is the tuple $(\Psi, (a, b))$ a number as returned by $-log(c((a,b)))$ (where $c$ simply assigns a number, usually $0$ or $1$, to the pair $(a,b)$? –  Felix Dombek Jan 24 '11 at 5:23
show 1 more comment

1 Answer

A forum power series is a "Symbolic series" and not necessarily one where the object the series is over is a "number".

The idea comes from group there where you have the operations of multiplication and addition in a ring. you can form the expressions a*x + b*x^2 + c*x^3, etc... e.g., the polynomials or P[x] but note x may not necessarily be in the ring. We can still write such expressions and take x as a sort of place holder or symbol

http://en.wikipedia.org/wiki/Polynomial_ring

http://en.wikipedia.org/wiki/Formal_power_series

The idea is an extension from the idea of a "normal" power series but applied to a "formal object". Those two links should clue you in on the exact meaning.

share|improve this answer
    
Sorry, the Wikipedia article didn't help me much :( –  Felix Dombek Jan 24 '11 at 5:26
    
Also, the form P[X] or P[[X]] is not in my paper at all. They just do the (S, (a, b)) = -log(c((a,b))) thing. I need some precise info on the stuff that's in this set, nothing else, otherwise it could fry my brains out! –  Felix Dombek Jan 24 '11 at 5:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.