Coverability in Two Dimensions - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2015

Coverability in Two Dimensions

Abstract

A word is quasiperiodic (or coverable) if it can be covered by occurrences of another finite word, called its quasiperiod. This notion was previously studied in the domains of text algorithms and combinatorics of right infinite words. We extend several results to two dimensions. We also characterize all rectangular words that cover non-periodic two-dimensional infinite words. Then we focus on two-dimensional words with infinitely many quasiperiods. We show that such words have zero entropy. However, contrarily to the one-dimensional case, they may not be uniformly recurrent.
Fichier principal
Vignette du fichier
cover-two-dimen.pdf (115.17 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01180026 , version 1 (28-06-2019)

Identifiers

Cite

Guilhem Gamard, Gwenaël Richomme. Coverability in Two Dimensions. 9th International Conference on Language and Automata Theory and Applications (LATA), Mar 2015, Nice, France. pp.402-413, ⟨10.1007/978-3-319-15579-1_31⟩. ⟨lirmm-01180026⟩
160 View
131 Download

Altmetric

Share

Gmail Facebook X LinkedIn More