Pal(k) is Linear Recognizable Online / Kosolobov Dmitry,Rubinchik Mikhail,Shur Arseny M. // . - 2015. - V. 8939, l. . - P. 289-301.

ISSN/EISSN:
0302-9743 / нет данных
Type:
Proceedings Paper
Abstract:
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.
Author keywords:
TIME; RECOGNITION; ALGORITHM
DOI:
нет данных
Web of Science ID:
ISI:000357679300023
Соавторы в МНС:
Другие поля
Поле Значение
Editor Italiano, GF and MargariaSteffen, T and Pokorny, J and Quisquater, JJ and Wattenhofer, R
Booktitle SOFSEM 2015: THEORY AND PRACTICE OF COMPUTER SCIENCE
Series Lecture Notes in Computer Science
Note 41st International Conference on Current Trends in Theory and Practice of Computer Science ((SOFSEM), Pecpod Snezkou, CZECH REPUBLIC, JAN 24-29, 2015
Organization Czech Soc Cybernet \& Informat
Publisher SPRINGER-VERLAG BERLIN
Address HEIDELBERGER PLATZ 3, D-14197 BERLIN, GERMANY
Language English
ISBN 978-3-662-46078-8; 978-3-662-46077-1
Keywords-Plus TIME; RECOGNITION; ALGORITHM
Research-Areas Computer Science
Web-of-Science-Categories Computer Science, Artificial Intelligence; Computer Science, Software Engineering; Computer Science, Theory \& Methods
Author-Email dkosolobov@mail.ru mikhail.rubinchik@gmail.com arseny.shur@urfu.ru
Number-of-Cited-References 13
Doc-Delivery-Number BD0SW