Small-Space Algorithms for the Online Language Distance Problem for Palindromes and Squares

Gabriel Bathie, Tomasz Kociumaka, Tatiana Starikovskaya

We study the online variant of the language distance problem for two classical formal languages, the language of palindromes and the language of squares, and for the two most funda…