An Hadamard operation on rational relations (Q517036)

The paper is about an operation, called the Hadamard star, on binary relations on the set \(\mathbb{N}\) of the nonnegative integers. A relation \(R \subseteq \mathbb{N}\times \mathbb{N}\) is said to be rational if it is rational as a subset of the additive monoid \(\mathbb{N}\times \mathbb{N}\), and the Hadamard star of \(R\) is the relation \(R^\otimes = \{(n,m_1 + \ldots +m_k) \mid k\geq 0, (n,m_i)\in R\}\). The author characterizes the rational relations \(R\) for which also \(R^\otimes\) is rational and shows that this property is decidable. With any relation \(R \subseteq \mathbb{N}\times \mathbb{N}\) one may associate a formal power series \(s = \sum_{n\geq 0}R(n)x^n\), where \(R(n) = \{m\in \mathbb{N} \mid (n,m) \in R\}\) for each \(n\in \mathbb{N}\). Since the relation \(R\) is rational if and only if the corresponding series \(s\) is \(\operatorname{Rat}(\mathbb{N})\)-rational, where \(\operatorname{Rat}(\mathbb{N})\) is the semiring of the rational subsets of the additive monoid \(\mathbb{N}\), the results of the paper can be interpreted also in terms of \(\operatorname{Rat}(\mathbb{N})\)-series.