1. Электронный научный архив УрФУ
  2. 00. Общеуниверситетские коллекции
  3. Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс: http://elar.urfu.ru/handle/10995/101705
Полная запись метаданных
Поле DCЗначениеЯзык
dc.contributor.authorGourdel, G.en
dc.contributor.authorKociumaka, T.en
dc.contributor.authorRadoszewski, J.en
dc.contributor.authorRytter, W.en
dc.contributor.authorShur, A.en
dc.contributor.authorWaleń, T.en
dc.date.accessioned2021-08-31T14:59:09Z-
dc.date.available2021-08-31T14:59:09Z-
dc.date.issued2020-
dc.identifier.citationString periods in the order-preserving model / G. Gourdel, T. Kociumaka, J. Radoszewski, et al. — DOI 10.1016/j.ic.2019.104463 // Information and Computation. — 2020. — Vol. 270. — 104463.en
dc.identifier.issn8905401-
dc.identifier.otherFinal2
dc.identifier.otherAll Open Access, Green3
dc.identifier.otherhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-85072028290&doi=10.1016%2fj.ic.2019.104463&partnerID=40&md5=b40577e5514f0706b5b61ecc2bdd3b48
dc.identifier.otherhttps://drops.dagstuhl.de/opus/volltexte/2018/8506/pdf/LIPIcs-STACS-2018-38.pdfm
dc.identifier.urihttp://elar.urfu.ru/handle/10995/101705-
dc.description.abstractIn the order-preserving model, two strings match if they share the same relative order between the characters at the corresponding positions. This model is quite recent, but it has already attracted significant attention because of its applications in data analysis. We introduce several types of periods in this setting (op-periods). Then we give algorithms to compute these periods in time O(n), O(nlog⁡log⁡n), O(nlog2⁡log⁡n/log⁡log⁡log⁡n), O(nlog⁡n) depending on the type of periodicity. In the most general variant, the number of different op-periods can be as big as Ω(n2), and a compact representation is needed. Our algorithms require novel combinatorial insight into the properties of op-periods. In particular, we characterize the Fine–Wilf property for coprime op-periods. © 2019 Elsevier Inc.en
dc.description.sponsorshipSupported by ISF grants no. 824/17 and 1278/16 and by an ERC grant MPM under the EU's Horizon 2020 Research and Innovation Programme (grant no. 683064).Supported by the Ministry of Science and Higher Education of the Russian Federation, project 1.3253.2017.A part of this work was done during the workshop StringMasters in Warsaw 2017 that was sponsored by the Warsaw Center of Mathematics and Computer Science. The authors thank the participants of the workshop, especially Hideo Bannai and Shunsuke Inenaga, for helpful discussions.en
dc.format.mimetypeapplication/pdfen
dc.language.isoenen
dc.publisherElsevier Inc.en
dc.rightsinfo:eu-repo/semantics/openAccessen
dc.sourceInf Comput2
dc.sourceInformation and Computationen
dc.subjectEFFICIENT ALGORITHMen
dc.subjectORDER-PRESERVING PATTERN MATCHINGen
dc.subjectPERIODen
dc.subjectCOMPUTATIONAL METHODSen
dc.subjectINFORMATION SYSTEMSen
dc.subjectCOMPACT REPRESENTATIONen
dc.subjectCOPRIMEen
dc.subjectITS APPLICATIONSen
dc.subjectORDER PRESERVINGen
dc.subjectPERIODen
dc.subjectRELATIVE ORDERen
dc.subjectPATTERN MATCHINGen
dc.titleString periods in the order-preserving modelen
dc.typeArticleen
dc.typeinfo:eu-repo/semantics/articleen
dc.typeinfo:eu-repo/semantics/publishedVersionen
dc.identifier.doi10.1016/j.ic.2019.104463-
dc.identifier.scopus85072028290-
local.contributor.employeeGourdel, G., Computer Science Department, ENS Paris-Saclay, Cachan, 5 rue Blaise Pascal, Bagneux, 92220, France
local.contributor.employeeKociumaka, T., Department of Computer Science, Bar Ilan University, Ramat Gan, 5290002, Israel, Institute of Informatics, University of Warsaw, Banacha 2, Warsaw, 02-097, Poland
local.contributor.employeeRadoszewski, J., Institute of Informatics, University of Warsaw, Banacha 2, Warsaw, 02-097, Poland
local.contributor.employeeRytter, W., Institute of Informatics, University of Warsaw, Banacha 2, Warsaw, 02-097, Poland
local.contributor.employeeShur, A., Department of Algebra and Fundamental Informatics, Ural Federal University, pr. Lenina 51, Ekaterinburg, 620000, Russian Federation
local.contributor.employeeWaleń, T., Institute of Informatics, University of Warsaw, Banacha 2, Warsaw, 02-097, Poland
local.volume270-
dc.identifier.wos000506427100006-
local.contributor.departmentComputer Science Department, ENS Paris-Saclay, Cachan, 5 rue Blaise Pascal, Bagneux, 92220, France
local.contributor.departmentDepartment of Computer Science, Bar Ilan University, Ramat Gan, 5290002, Israel
local.contributor.departmentInstitute of Informatics, University of Warsaw, Banacha 2, Warsaw, 02-097, Poland
local.contributor.departmentDepartment of Algebra and Fundamental Informatics, Ural Federal University, pr. Lenina 51, Ekaterinburg, 620000, Russian Federation
local.identifier.purebbd4ec15-75f0-45e7-a98a-ca743f77cfe6uuid
local.identifier.pure11901729-
local.description.order104463-
local.identifier.eid2-s2.0-85072028290-
local.fund.cordis683064-
local.identifier.wosWOS:000506427100006-
Располагается в коллекциях:Научные публикации ученых УрФУ, проиндексированные в SCOPUS и WoS CC

Файлы этого ресурса:
Файл Описание РазмерФормат 
2-s2.0-85072028290.pdf616,22 kBAdobe PDFПросмотреть/Открыть
Показать базовое описание ресурса Статистика


Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.