# 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].

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