Аддитивной сложностью слова называется длина кратчайшей схемы конкатенации, порождающей это слово. Для слов длины n, удовлетворяющих различным ограничениям на состав подслов, получены асимптотические (при n→∞) верхние оценки аддитивной сложности. Показано, что эти оценки неулучшаемы для наиболее сложных слов из рассматриваемых множеств.
展开▼
