Let $\Sigma$ be a finite alphabet, and consider the formel power series over $\Sigma$ considered as non-commuting variables with coefficients in the semiring $\mathcal N := \mathbb N \cup \{\infty\}$ with $$ n \cdot \infty = \infty\cdot n = \infty \mbox{ for all $n \ne 0$, } \qquad \infty\cdot \infty = \infty \qquad n + \infty = \infty + n = \infty \mbox{ for all $n$, } \qquad 0\cdot \infty = \infty\cdot 0 = 0 \qquad \infty + \infty = \infty. $$

A formal power series is a polynomial if only a finite number of coefficients are non-zero. A formel power series is called rational if it could be built up from polynomials by a finite application of addition (pointwise), multiplication (convolutional product), and the star operatation, which for $f = \sum_{w \in \Sigma^{\ast}} c_w w$ is defined by $$ f^{\ast} = 1 + f + f^2 + f^3 + \ldots $$ where the sum taken over an infinite set $\{ k_i \in \mathcal N \mid i \in I \}$ is defined as $\sup\{ \sum_{j\in J} k_j \mid J\subseteq I \mbox{ finite } \}$, i.e. the supremum of all finite sums, hence the above expression makes sense.

These notions go back to Schützenberger and Eilenburg, where the last one calls these $\mathcal N$-subsets instead of formal power series. Now given $f$ we define $$ xf_s := \left\{ \begin{array}{ll} \infty & xf = \infty \\ 0 & \mbox{ otherwise.} \end{array}\right. $$ the singular part, i.e. all entries whose coefficient is $\infty$ are retained, and $$ xf_n := \left\{ \begin{array}{ll} xf & xf \ne \infty \\ 0 & \mbox{ otherwise } \end{array} \right. $$ the non-singular part, where we retain those entries that do not evaluate to $\infty$. Surely $$ f = f_s + f_n $$ and we have \begin{align*} (f + g)_s & = f_s + g_s \\ (f g)_s & = f_s g + g_s f. \end{align*}

Now let $\mathcal C$ be the class of formal power series $f$ such that $f_s$ is rational, then why does the above formula imply that $\mathcal C$ is closed under multiplication?

The argument is taken from Samuel Eilenberg, Automata, Machines, Languages, Volume A to show that for rational $f$, also $f_s$ and $f_n$ are rational, and he uses exactly the above argument. Buf if $f_s$ is rational, and $g$ such that $g_s$ is rational, why should then $f_s g + f g_s$ be rational?

  • $\begingroup$ Isn't it the case that if $f$ and $f_s$ are rational then so is $f_n$? $\endgroup$ – Michaël Cadilhac Jul 5 '18 at 16:13
  • 1
    $\begingroup$ I do not think so, rational languages/power series are in general not closed under complement, but even if this would hold, then how is it related to my question? $\endgroup$ – StefanH Jul 5 '18 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.