4551
правка
Сравнение с шаблоном для сжатого текста: различия между версиями
Перейти к навигации
Перейти к поиску
Сравнение с шаблоном для сжатого текста (посмотреть исходный код)
Версия от 13:42, 5 ноября 2021
, 5 ноября 2021→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
<math>a</math> для <math>a \in \Sigma \cup \{ \epsilon \}</math> (примитивное присваивание) | <math>a</math> для <math>a \in \Sigma \cup \{ \epsilon \}</math> (примитивное присваивание) | ||
<math>X_i X_j</math> для i,j< k (конкатенация) | <math>X_i X_j</math> для i,j < k (конкатенация) | ||
[j] | <math>^{[j]}X_i</math> для i < k и целого положительного числа j (усечение префикса длины j) | ||
<math>X_i^{[j]}</math> для i < k и целого положительного числа j (усечение суффикса длины j) | |||
( | <math>(X_i)^j</math> для i < k и положительного целого числа ј (j-кратное повторение) | ||
Под усечением префикса (или суффикса) длины j мы понимаем операцию над строками, которая берет строку w и возвращает строку, полученную из w путем удаления ее префикса (или суффикса) длины j. Переменные | Под ''усечением префикса (или суффикса) длины j'' мы понимаем операцию над строками, которая берет строку w и возвращает строку, полученную из w путем удаления ее префикса (или суффикса) длины j. Переменные <math>X_k</math> представляют строки <math>\bar{X_k}</math>, полученные путем оценки их выражений. ''Размером'' <math>\mathcal{D}</math> является количество n присваиваний, обозначаемое <math>|\mathcal{D}|</math>. обозначим за <math>height(\mathcal{D})</math> максимальную зависимость в <math>\mathcal{D}</math>. <math>\mathcal{S}</math> – это последовательность <math>X_{i_1} ... X_{j_\ell}</math> переменных, определенных в <math>\mathcal{D}</math>. ''Длина'' <math>\mathcal{S}</math> представляет собой количество <math>\ell</math> переменных в <math>\mathcal{S}</math> и обозначается <math>|\mathcal{S}|</math>. Таким образом, можно считать, что <math>|\mathbf{c}(T)| = |\mathcal{D}| + |\mathcal{S}|</math>. | ||