Recognizability of the support of recognizable series over the semiring of the integers is undecidable
A recognizable series over the semiring of the integers is a function that maps each word over an alphabet to an integer. The support of such a series consists of all those words which are not mapped to zero. It is long known that there are recognizable series whose support is not a recognizable, but a context-free language. However, the problem of deciding whether the support of a given recognizable series is recognizable was never considered. Here we show that this problem is undecidable. The proof relies on an encoding of an instance of Postʼs correspondence problem.