|
Записки научных семинаров ЛОМИ, 1976, том 60, страницы 65–74
(Mi znsl2071)
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 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 назв.
Образец цитирования:
С. Ю. Маслов, “Отношение поглощения на регулярных множествах”, Исследования по конструктивной математике и математической логике. VII, Зап. научн. сем. ЛОМИ, 60, Изд-во «Наука», Ленинград. отд., Л., 1976, 65–74; J. Soviet Math., 14:5 (1980), 1468–1475
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/znsl2071 https://www.mathnet.ru/rus/znsl/v60/p65
|
Статистика просмотров: |
Страница аннотации: | 199 | PDF полного текста: | 80 |
|