${\mathrm{Pal}}^k$ Is Linear Recognizable Online

Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur

Given a language $L$ that is online recognizable in linear time and space, we construct a linear time and space online recognition algorithm for the language $L\cdot \mathrm{Pal}$,…