An output-sensitive algorithm for the minimization of 2-dimensional string covers

Alexandru Popa, Andrei Tanasescu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

String covers are a powerful tool for analyzing the quasi-periodicity of 1-dimensional data and find applications in automata theory, computational biology, coding and the analysis of transactional data. A cover of a string T is a string C for which every letter of T lies within some occurrence of C. String covers have been generalized in many ways, leading to k-covers, λ -covers, approximate covers and were studied in different contexts such as indeterminate strings. In this paper we generalize string covers to the context of 2-dimensional data, such as images. We show how they can be used for the extraction of textures from images and identification of primitive cells in lattice data. This has interesting applications in image compression, procedural terrain generation and crystallography.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
EditorsT. V. Gopal, Junzo Watada
PublisherSpringer Verlag
Pages536-549
Number of pages14
ISBN (Print)9783030148119
DOIs
Publication statusPublished - Jan 1 2019
Event15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan
Duration: Apr 13 2019Apr 16 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11436 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
CountryJapan
CityKitakyushu
Period4/13/194/16/19

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Popa, A., & Tanasescu, A. (2019). An output-sensitive algorithm for the minimization of 2-dimensional string covers. In T. V. Gopal, & J. Watada (Eds.), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings (pp. 536-549). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14812-6_33