Аннотация:
Пусть $R$ – регулярное выражение (которое строится обычным
образом из букв алфавита $A$ при помощи операций $\cdot$, $\vee$ и $\{\}$), $R$ –
соответствующее регулярное (распознаваемое конечным автоматом)
множество слов в $A$. Для слов $P$ и $Q$ из $R$ определяется отношение
$P\prec_RQ$ ($QR$ – поглощает $P$), удовлетворяющее следующим
условиям:
1) $P\prec_RP$, $\Lambda\prec_{\{R\}}P$ ($\Lambda$ – пустое слово);
2) если $P\prec_{R_1}Q$, то $P\prec_{R_1\vee R_2}Q$, $P\prec_{R_2\vee R_1}Q$, $P\prec_{\{R_1\}}Q$;
3) если $P_1\prec_{R_1}Q_1$ и $P_1\prec_{R_2}Q_2$, то $P_1P_2\prec_{R_1\cdot R_2}Q_1Q_2$;
4) если $P_1\prec_{\{R\}}Q_1$ и $P_2\prec_{\{R\}}Q_2$, то $P_1P_2\prec_{\{R\}}Q_1Q_2$.
ТЕОРЕМА. Для любого $R$ и любой бесконечной последовательности
слов из $R$ существует такая бесконечная подпоследовательность,
что $P_1\prec_RP_2\prec_RP_3\prec_R\dots$ .
Результаты этого рода оказались применимы к доказательствам
разрешимости некоторых канонических исчислений, возникающих при
моделировании биологической эволюции. Библ. 6 назв.