Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102219
Title: The Number of Distinct Subpalindromes in Random Words
Authors: Rubinchik, M.
Shur, A. M.
Issue Date: 2016
Publisher: IOS Press
Citation: Rubinchik M. The Number of Distinct Subpalindromes in Random Words / M. Rubinchik, A. M. Shur. — DOI 10.3233/FI-2016-1366 // Fundamenta Informaticae. — 2016. — Vol. 145. — Iss. 3. — P. 371-384.
Abstract: We prove that a random word of length n over a k-Ary fixed alphabet contains, on expectation, Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞(n,k)/√n does not exist for any k ≥ 2, liminfn→∞(n,k)/ √n=Θ(1), and limsupn→∞(n,k)/ √n=Θ(k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.
Keywords: INFORMATION SYSTEMS
NUMBER OF FACTORS
ODD LENGTH
PALINDROMIC
COMPUTATIONAL METHODS
URI: http://hdl.handle.net/10995/102219
Access: info:eu-repo/semantics/openAccess
SCOPUS ID: 84984917783
PURE ID: 1097440
41be7078-f54d-4790-ad6a-57d97b1baac5
ISSN: 1692968
DOI: 10.3233/FI-2016-1366
Appears in Collections:Научные публикации, проиндексированные в SCOPUS и WoS CC

Files in This Item:
File Description SizeFormat 
2-s2.0-84984917783.pdf168,2 kBAdobe PDFView/Open


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