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

Strings
Automata theory
Cover
Crystallography
Output
Image compression
Textures
Quasiperiodicity
Automata Theory
Computational Biology
Image Compression
Texture
Coding
Generalise
Cell
Context

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

An output-sensitive algorithm for the minimization of 2-dimensional string covers. / Popa, Alexandru; Tanasescu, Andrei.

Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. ed. / T. V. Gopal; Junzo Watada. Springer Verlag, 2019. p. 536-549 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS).

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

Popa, A & Tanasescu, A 2019, An output-sensitive algorithm for the minimization of 2-dimensional string covers. in TV Gopal & J Watada (eds), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11436 LNCS, Springer Verlag, pp. 536-549, 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019, Kitakyushu, Japan, 4/13/19. https://doi.org/10.1007/978-3-030-14812-6_33
Popa A, Tanasescu A. An output-sensitive algorithm for the minimization of 2-dimensional string covers. In Gopal TV, Watada J, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Springer Verlag. 2019. p. 536-549. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-14812-6_33
Popa, Alexandru ; Tanasescu, Andrei. / An output-sensitive algorithm for the minimization of 2-dimensional string covers. Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. editor / T. V. Gopal ; Junzo Watada. Springer Verlag, 2019. pp. 536-549 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{f53ba960f9da475c99cf6e0c04aaf4e5,
title = "An output-sensitive algorithm for the minimization of 2-dimensional string covers",
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.",
author = "Alexandru Popa and Andrei Tanasescu",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-14812-6_33",
language = "English",
isbn = "9783030148119",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "536--549",
editor = "Gopal, {T. V.} and Junzo Watada",
booktitle = "Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings",
address = "Germany",

}

TY - GEN

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

AU - Popa, Alexandru

AU - Tanasescu, Andrei

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85064874787&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064874787&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14812-6_33

DO - 10.1007/978-3-030-14812-6_33

M3 - Conference contribution

SN - 9783030148119

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 536

EP - 549

BT - Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings

A2 - Gopal, T. V.

A2 - Watada, Junzo

PB - Springer Verlag

ER -