Take the 2-minute tour ×

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
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

1 Answer 1

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 $ax + bx^2 + cx^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

Polynomial ring

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

Your Answer


