Affordable Access

Publisher Website

A multidimensional critical factorization theorem

Authors
Journal
Theoretical Computer Science
0304-3975
Publisher
Elsevier
Publication Date
Volume
346
Identifiers
DOI: 10.1016/j.tcs.2005.08.012
Keywords
  • Combinatorics On Words
  • Periodicity
  • Multidimensional Words
Disciplines
  • Mathematics

Abstract

Abstract The Critical Factorization Theorem is one of the principal results in combinatorics on words. It relates local periodicities of a word to its global periodicity. In this paper we give a multidimensional extension of it. More precisely, we give a new proof of the Critical Factorization Theorem, but in a weak form, where the weakness is due to the fact that we loose the tightness of the local repetition order. In exchange, we gain the possibility of extending our proof to the multidimensional case. Indeed, this new proof makes use of the Theorem of Fine and Wilf, that has several classical generalizations to the multidimensional case.

There are no comments yet on this publication. Be the first to share your thoughts.