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

EPIFANIO C, F MIGNOSI (2005). A Multidimensional Critical Factorization Theorem. THEORETICAL COMPUTER SCIENCE, 346(2-3), 265-280 [10.1016/j.tcs.2005.08.012].

A Multidimensional Critical Factorization Theorem

EPIFANIO, Chiara;MIGNOSI, Filippo
2005-01-01

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
2005
EPIFANIO C, F MIGNOSI (2005). A Multidimensional Critical Factorization Theorem. THEORETICAL COMPUTER SCIENCE, 346(2-3), 265-280 [10.1016/j.tcs.2005.08.012].
File in questo prodotto:
File Dimensione Formato  
mignosi.pdf

accesso aperto

Dimensione 159.08 kB
Formato Adobe PDF
159.08 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/12418
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact