Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Coverability in Two Dimensions
verfasst von : Guilhem Gamard, Gwenaël Richomme
Erschienen in: Language and Automata Theory and Applications
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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.