Please use this identifier to cite or link to this item: http://hdl.handle.net/10995/102219
Full metadata record
DC FieldValueLanguage
dc.contributor.authorRubinchik, M.en
dc.contributor.authorShur, A. M.en
dc.date.accessioned2021-08-31T15:02:33Z-
dc.date.available2021-08-31T15:02:33Z-
dc.date.issued2016-
dc.identifier.citationRubinchik 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.en
dc.identifier.issn1692968-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84984917783&doi=10.3233%2fFI-2016-1366&partnerID=40&md5=bd0906dd173a10ada8ea479b9b28fe42
dc.identifier.otherhttp://arxiv.org/pdf/1505.08043m
dc.identifier.urihttp://hdl.handle.net/10995/102219-
dc.description.abstractWe 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.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherIOS Pressen
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceFundam Inf2
dc.sourceFundamenta Informaticaeen
dc.subjectINFORMATION SYSTEMSen
dc.subjectNUMBER OF FACTORSen
dc.subjectODD LENGTHen
dc.subjectPALINDROMICen
dc.subjectCOMPUTATIONAL METHODSen
dc.titleThe Number of Distinct Subpalindromes in Random Wordsen
dc.typeConference Paperen
dc.typeinfo:eu-repo/semantics/conferenceObjecten
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.3233/FI-2016-1366-
dc.identifier.scopus84984917783-
local.contributor.employeeRubinchik, M., Ural Federal University, Ekaterinburg, Russian Federation
local.contributor.employeeShur, A.M., Ural Federal University, Ekaterinburg, Russian Federation
local.description.firstpage371-
local.description.lastpage384-
local.issue3-
local.volume145-
local.contributor.departmentUral Federal University, Ekaterinburg, Russian Federation
local.identifier.pure1097440-
local.identifier.pure41be7078-f54d-4790-ad6a-57d97b1baac5uuid
local.identifier.eid2-s2.0-84984917783-
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.