Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Rectangular Tile Covers of 2D-Strings

Uproszczony widok
cris.lastimport.scopus2024-02-12T19:50:09Z
dc.abstract.enWe consider tile covers of 2D-strings which are a generalization of periodicity of 1D-strings. We say that a 2D-string A is a tile cover of a 2D-string S if S can be decomposed into non-overlapping 2D-strings, each of them equal to A or to A^T, where A^T is the transpose of A. We show that all tile covers of a 2D-string of size N can be computed in (N^{1+ε}) time for any ε > 0. We also show a linear-time algorithm for computing all 1D-strings being tile covers of a 2D-string.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2022-06-29
dc.conference.datestart2022-06-27
dc.conference.placePraga
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesCombinatorial Pattern Matching
dc.conference.seriesshortcutCPM
dc.conference.shortcutCPM 2022
dc.conference.weblinkhttps://www.stringology.org/event/CPM2022/
dc.contributor.authorZuba, Wiktor
dc.contributor.authorWaleń, Tomasz
dc.contributor.authorStraszyński, Juliusz
dc.contributor.authorRytter, Wojciech
dc.contributor.authorRadoszewski, Jakub
dc.date.accessioned2024-01-25T19:08:10Z
dc.date.available2024-01-25T19:08:10Z
dc.date.copyright2022-06-22
dc.date.issued2022
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.CPM.2022.23
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/118059
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2022/16150/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages23:1--23:14
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleRectangular Tile Covers of 2D-Strings
dc.typeJournalArticle
dspace.entity.typePublication