RUS  ENG
Полная версия
ЖУРНАЛЫ // Записки научных семинаров ПОМИ // Архив

Зап. научн. сем. ЛОМИ, 1976, том 60, страницы 65–74 (Mi znsl2071)

Эта публикация цитируется в 1 статье

Отношение поглощения на регулярных множествах

С. Ю. Маслов


Аннотация: Пусть $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 назв.

УДК: 51.01:164


 Англоязычная версия: Journal of Soviet Mathematics, 1980, 14:5, 1468–1475

Реферативные базы данных:


© МИАН, 2024