6533b82ffe1ef96bd1295bf5
RESEARCH PRODUCT
On a Conjecture on Bidimensional Words
Chiara EpifanioMichel KoskasFilippo Mignosisubject
Discrete mathematicsConjectureGeneral Computer ScienceExistential quantificationTheoretical Computer ScienceCombinatoricsCombinatorics on wordsFormal languageComplexity functionPattern matchingAlphabetDouble sequenceComputer Science(all)Mathematicsdescription
We prove that, given a double sequence w over the alphabet A (i.e. a mapping from Z2 to A), if there exists a pair (n0, m0) ∈ Z2 such that pw(n0, m0) < 1/100n0m0, then w has a periodicity vector, where pw is the complexity function in rectangles of w.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2003-04-01 |