Absoluteness of subword inequality is undecidable
classification
💻 cs.FL
keywords
givenproblemsubwordundecidableabsolutenessalphabetaskedassumes
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.