A NOTE ON THE DECIDABILITY OF SUBWORD INEQUALITIES
Szilárd Zsolt Fazekas, Robert Mercaş · International Journal of Foundations of Computer Science · 2013
Extending the general undecidability result concerning the absoluteness of inequalities between subword histories, in this paper we show that the question whether such inequalities hold for all words is undecidable even over a binary alphabet and bounded number of blocks, i.e., unary factors of maximal length.