zbMATH — the first resource for mathematics

\(\mathrm{Pal}^{k}\) is linear recognizable online. (English) Zbl 1432.68228
Italiano, Giuseppe F. (ed.) et al., SOFSEM 2015: theory and practice of computer science. 41st international conference on current trends in theory and practice of computer science, Pec pod Sněžkou, Czech Republic, January 24–29, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8939, 289-301 (2015).
Summary: 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}\), where Pal is the language of all nonempty palindromes. Hence for every fixed positive \(k\), \(\mathrm{Pal}^{k}\) is online recognizable in linear time and space. Thus we solve an open problem posed by Z. Galil and J. Seiferas in [J. Assoc. Comput. Mach. 25, 102–111 (1978; Zbl 0365.68058)].
For the entire collection see [Zbl 1303.68019].

68Q45 Formal languages and automata
68R15 Combinatorics on words
68W27 Online algorithms; streaming algorithms
68W40 Analysis of algorithms
Full Text: DOI