Pal^k is linear recognizable online

DOI10.1007/978-3-662-46078-8_24MaRDI QIDQ5175115zbMATH OpenOpenAlexFDO

Authors Dmitry Kosolobov, Mikhail Rubinchik, Arseny M. Shur

Publication date 20 February 2015

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5244

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40)

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 $LcdotmathrmPal$, where $mathrmPal$ 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 Galil and Seiferas in 1978.

Recommendations

• Approximate On-line Palindrome Recognition, and Applications
• Palindromic length in linear time
• The derivation of on-line algorithms, with an application to finding palindromes
• Open problems related to palindrome recognition: are there open problems related to palindrome recognition?
• Computing palindromic factorizations and palindromic covers on-line

Cited in

(14)

• Computing longest palindromic substring after single-character or block-wise edits
• Palindromic decompositions with gaps and errors
• Diverse Palindromic Factorization is NP-Complete
• Upper bound for palindromic and factor complexity of rich words
• scientific article; zbMATH DE number 7559452 (Why is no real title available?)
• Detecting one-variable patterns
• Counting palindromes in substrings
• Palindromic decompositions with gaps and errors
• Open problems related to palindrome recognition: are there open problems related to palindrome recognition?
• Maximal degenerate palindromes with gaps and mismatches
• Double-ended palindromic trees in linear time
• Palindromic length of infinite aperiodic words
• Small space encoding and recognition of k-palindromic prefixes
• Palindromic rich words and run-length encodings

This page was built for publication: \(\mathrm{Pal}^{k}\) is linear recognizable online

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175115)