Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 3. UTUCris-artikkelit
  • Rinnakkaistallenteet
  • Näytä aineisto
  •   Etusivu
  • 3. UTUCris-artikkelit
  • Rinnakkaistallenteet
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

The most unbalanced words 0q−p1p and majorization

Jetro Vesti

The most unbalanced words 0q−p1p and majorization

Jetro Vesti
Katso/Avaa
Author's Post-print (208.3Kb)
Lataukset: 

World Scientific
doi:10.1142/S1793830915500287
URI
http://www.worldscientific.com/toc/dmaa/07/03
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2021042715001
Tiivistelmä


A finite word w ∈ {0, 1}∗ is balanced if for every equal-length factors u and v of every

cyclic shift of w we have ||u|1 − |v|1| ≤ 1. This new class of finite words was defined in

[O. Jenkinson and L. Q. Zamboni, Characterisations of balanced words via orderings,

Theoret. Comput. Sci. 310(1–3) (2004) 247–271]. In [O. Jenkinson, Balanced words and

majorization, Discrete Math. Algorithms Appl. 1(4) (2009) 463–484], there was proved

several results considering finite balanced words and majorization. One of the main

results was that the base-2 orbit of the balanced word is the least element in the set of

orbits with respect to partial sum. It was also proved that the product of the elements

in the base-2 orbit of a word is maximized precisely when the word is balanced. It turns

out that the words 0q−p1p have similar extremal properties, opposite to the balanced

words, which makes it meaningful to call these words the most unbalanced words. This

paper contains the counterparts of the results mentioned above. We will prove that the

orbit of the word u = 0q−p1p is the greatest element in the set of orbits with respect

to partial sum and that it has the smallest product. We will also prove that u is the

greatest element in the set of orbits with respect to partial product.

Kokoelmat
  • Rinnakkaistallenteet [19206]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste