Pal k is Linear Recognizable Online
Pal k is Linear Recognizable Online
复制标题
Pal k 是可在线线性识别的
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Shur
中科院分区：
文献类型：
--
作者：
D. Kosolobov;Mikhail Rubinchik;A. Shur
给定一个在线性时空中可在线识别的语言L，我们构造了一个语言L·L的线性时空在线识别算法，其中L·L是所有非空回文的语言.因此，对于每一个固定的正k，k是线性时间和空间中在线可识别的。因此，我们解决了Galil和Seiferas在1978年提出的一个公开问题。
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·Pal, where Pal is the language of all nonempty palindromes. Hence for every fixed positive k, Pal k is online recognizable in linear time and space. Thus we solve an open problem posed by Galil and Seiferas in 1978.