Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102405
Title: Palk is linear recognizable online
Authors: Kosolobov, D.
Rubinchik, M.
Shur, A. M.
Issue Date: 2015
Publisher: Springer Verlag
Citation: Kosolobov D. Palk is linear recognizable online / D. Kosolobov, M. Rubinchik, A. M. Shur. — DOI 10.1007/978-3-662-46078-8_24 // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). — 2015. — Vol. 8939. — P. 289-301.
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, Palk is online recognizable in linear time and space. Thus we solve an open problem posed by Galil and Seiferas in 1978. © Springer-Verlag Berlin Heidelberg 2015.
Keywords: COMPUTER SCIENCE
COMPUTERS
LINEAR TIME
ON-LINE RECOGNITION
ARTIFICIAL INTELLIGENCE
URI: http://hdl.handle.net/10995/102405
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84922021476
PURE ID: 607817
90808054-adc4-491b-9838-a4c93402cb92
ISSN: 3029743
ISBN: 9783662460771
DOI: 10.1007/978-3-662-46078-8_24
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84922021476.pdf245,46 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.