6533b851fe1ef96bd12a90a9
RESEARCH PRODUCT
A multidimensional critical factorization theorem
Filippo MignosiChiara Epifaniosubject
PeriodicityGeneral Computer ScienceRepetition (rhetorical device)Combinatorics on wordsExtension (predicate logic)Bruck–Ryser–Chowla theoremTheoretical Computer ScienceAlgebrasymbols.namesakeCombinatorics on wordsFactorizationMultidimensional wordsWeierstrass factorization theoremsymbolsOrder (group theory)Word (computer architecture)MathematicsComputer Science(all)description
AbstractThe 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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2005-11-01 | Theoretical Computer Science |