Записки научных семинаров ЛОМИ
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Зап. научн. сем. ПОМИ:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Записки научных семинаров ЛОМИ, 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 назв.
Англоязычная версия:
Journal of Soviet Mathematics, 1980, Volume 14, Issue 5, Pages 1468–1475
DOI: https://doi.org/10.1007/BF01693979
Реферативные базы данных:
УДК: 51.01:164
Образец цитирования: С. Ю. Маслов, “Отношение поглощения на регулярных множествах”, Исследования по конструктивной математике и математической логике. VII, Зап. научн. сем. ЛОМИ, 60, Изд-во «Наука», Ленинград. отд., Л., 1976, 65–74; J. Soviet Math., 14:5 (1980), 1468–1475
Цитирование в формате AMSBIB
\RBibitem{Mas76}
\by С.~Ю.~Маслов
\paper Отношение поглощения на регулярных множествах
\inbook Исследования по конструктивной математике и математической логике.~VII
\serial Зап. научн. сем. ЛОМИ
\yr 1976
\vol 60
\pages 65--74
\publ Изд-во «Наука», Ленинград. отд.
\publaddr Л.
\mathnet{http://mi.mathnet.ru/znsl2071}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=660299}
\zmath{https://zbmath.org/?q=an:0449.68019|0355.94061}
\transl
\jour J. Soviet Math.
\yr 1980
\vol 14
\issue 5
\pages 1468--1475
\crossref{https://doi.org/10.1007/BF01693979}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/znsl2071
  • https://www.mathnet.ru/rus/znsl/v60/p65
  • Эта публикация цитируется в следующих 1 статьяx:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Записки научных семинаров ПОМИ
    Статистика просмотров:
    Страница аннотации:199
    PDF полного текста:80
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024