Absoluteness of subword inequality is undecidable
Shinnosuke Seki · arXiv (Cornell University) · 2011
Mateescu, Salomaa, and Yu asked: is it decidable whether a given subword history assumes only non-negative values for all words over a given alphabet. In this paper, we solve this open problem by proving that this problem is undecidable even under stronger conditions than supposed originally.