Academic
Publications
Recognizability of the support of recognizable series over the semiring of the integers is undecidable

Recognizability of the support of recognizable series over the semiring of the integers is undecidable,10.1016/j.ipl.2011.02.014,Information Processin

Recognizability of the support of recognizable series over the semiring of the integers is undecidable   (Citations: 1)
BibTex | RIS | RefWorks Download
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.
Journal: Information Processing Letters - IPL , vol. 111, no. 10, pp. 500-502, 2011
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
Sort by: