Absoluteness of subword inequality is undecidable

In a given word, one can count the number of occurrences of other words as a scattered subword. These counts can be “added” and/or “multiplied.” A subword history gives an instruction of what words to be counted and how these counts to be added and multiplied with other counts or integer constants, and hence, determines its unique value in a given word. Mateescu, Salomaa, and Yu asked: “is it decidable whether the value of a given subword history is non-negative in all words over a given alphabet?” (absoluteness problem). Another important problem is of whether there exists a word in which the value of a given subword history becomes 0 (equality problem). In this paper, we prove the undecidability of the equality problem and show that the equality problem is polynomial-time Karp reducible to the absoluteness problem; thus, the absoluteness problem is also undecidable. This approach solves the open problem actually under stronger conditions than supposed originally.