<p>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. 
$$</p>

<p>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.</p>

<p>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 &amp; xf = \infty \\
   0     &amp; \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 &amp; xf \ne \infty \\
    0  &amp; \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 &amp; = f_s + g_s \\
 (f g)_s &amp; = f_s g + g_s f.
\end{align*}</p>

<p>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?</p>

<p>The argument is taken from <a href="https://books.google.de/books?id=NFFDQt67wgAC&amp;lpg=PA242&amp;ots=i9qEA_281f&amp;dq=%22purely%20singular%22%20rational%20language&amp;hl=de&amp;pg=PA189#v=onepage&amp;q=%22purely%20singular%22%20rational%20language&amp;f=false" rel="nofollow noreferrer">Samuel Eilenberg, Automata, Machines, Languages, Volume A</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?</p>

CC BY-SA 4.0
2018-07-05T16:13:20.417Z
Isn't it the case that if $f$ and $f_s$ are rational then so is $f_n$?
Michaël Cadilhac
CC BY-SA 4.0
2018-07-05T22:25:54.780Z
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?
StefanH
<fl.formal-languages><automata-theory><regular-language><algebra>
Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part
StefanH
# Rational power series over $\mathbb N \cup \{\infty\}$, rationality of singular part

(Asked by: username_0 on 2018-07-05)

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](https://books.google.de/books?id=NFFDQt67wgAC&lpg=PA242&ots=i9qEA_281f&dq=%22purely%20singular%22%20rational%20language&hl=de&pg=PA189#v=onepage&q=%22purely%20singular%22%20rational%20language&f=false) 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?

**Tags:** fl.formal-languages, automata-theory, regular-language, algebra
> **Comments:**
> **username_1**: Isn't it the case that if $f$ and $f_s$ are rational then so is $f_n$?  
> **username_0**: 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?  

---

## 0 answers

