Publikace na Matematicko-fyzikální fakulta |
2005
Abstrakt
Uvažujeme délku L nejdelší společné podposloupnosti dvou náhodných nezávislých n-znakových slov nad abecedou velikosti k. Ze subaditivity plyne, že střední hodnota L dělená n konverguje ke konstantě.
Určíme limitu hodnot konstanty pro k jdoucí do nekonečna, čímž dokážeme domněnku Sankoffa a Mainvilla z 80. let.