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

Alexandru Popa; Andrei Tanasescu

doi:10.1007/978-3-030-14812-6_33

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

Alexandru Popa, Andrei Tanasescu

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
Editors	T. V. Gopal, Junzo Watada
Publisher	Springer Verlag
Pages	536-549
Number of pages	14
ISBN (Print)	9783030148119
DOIs	https://doi.org/10.1007/978-3-030-14812-6_33
Publication status	Published - Jan 1 2019
Event	15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan Duration: Apr 13 2019 → Apr 16 2019

Publication series

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

Conference

Conference	15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
Country	Japan
City	Kitakyushu
Period	4/13/19 → 4/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

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 proceeding › Conference 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 = jan

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",

note = "15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 ; Conference date: 13-04-2019 Through 16-04-2019",

}

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

AN - SCOPUS:85064874787

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

T2 - 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019

Y2 - 13 April 2019 through 16 April 2019

ER -

Access to Document

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