153
правки
Изменения
Нет описания правки
|definition=
Существует упорядоченная пара конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>( i_1 , \ldots , i_k )</tex>, удовлетворяющей условию <tex>a_{i_1} \ldots a_{i_k} = b_{i_1} \ldots b_{i_k}</tex>, где <tex> 1 \leq i_j \leq n</tex> для каждого j, называется '''проблемой соответствий Поста (ПСП)'''.
}}
{{Определение
|definition=
'''Модифицированной проблемой соответствий Поста (МПСП)''' называется вопрос существования последовательности индексов <tex>( 1 , i_1, \ldots , i_k )</tex>, удовлетворяющих условию <tex>a_1 a_{i_1} \ldots a_{i_k} = b_1 b_{i_1} \ldots b_{i_k}, </tex> при <tex> 1 \leq i_j \leq n</tex> <tex>\forall j</tex> для упорядоченной пары конечных последовательностей <tex>(( a_1 , \ldots , a_n ) , ( b_1 , \ldots , b_n ))</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> <tex>\forall i</tex>.
}}
