Coverability in Two Dimensions

Guilhem Gamard 1 Gwenaël Richomme 1, 2
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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.
Type de document :
Communication dans un congrès
Adrian Horia Dediu; Enrico Formenti; Carlos Martín-Vide; Bianca Truthe. LATA: Language and Automata Theory and Applications, Mar 2015, Nice, France. Springer, 9th International Conference on Language and Automata Theory and Applications, 8977, 2015, LNCS. 〈http://grammars.grlmc.com/lata2015/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01180026
Contributeur : Gwenaël Richomme <>
Soumis le : jeudi 23 juillet 2015 - 20:14:46
Dernière modification le : jeudi 24 mai 2018 - 15:59:23

Identifiants

  • HAL Id : lirmm-01180026, version 1

Citation

Guilhem Gamard, Gwenaël Richomme. Coverability in Two Dimensions. Adrian Horia Dediu; Enrico Formenti; Carlos Martín-Vide; Bianca Truthe. LATA: Language and Automata Theory and Applications, Mar 2015, Nice, France. Springer, 9th International Conference on Language and Automata Theory and Applications, 8977, 2015, LNCS. 〈http://grammars.grlmc.com/lata2015/〉. 〈lirmm-01180026〉

Partager

Métriques

Consultations de la notice

102