• Март 31, 2008
• Павел Карпович
• О монотонной сложности пары слов
• Аннотация
• Будет дано определение монотонной сложности пары слов. Мы докажем, что монотонная сложность пары слов x,y превосходит сумму длин x и y не более чем на \alpha log(|x| + |y|) + O(1) для \alpha > 1 (для \alpha меньше 1 аналогичное утверждение неверно).