Семинары
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Календарь
Поиск
Регистрация семинара

RSS
Ближайшие семинары




Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
28 октября 2024 г. 16:00–17:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
 


Выразительная сила категориальных грамматик с однозначным присвоением категорий

М. Е. Вишникин

Московский государственный университет имени М. В. Ломоносова
Видеозаписи:
MP4 3,684.8 Mb

Количество просмотров:
Эта страница:100
Видеофайлы:20



Аннотация: Категориальная грамматика – это классический формализм для описания формальных языков. Идея заключается в том, чтобы каждому символу присвоить одну или несколько категорий, и слово принадлежит языку порождающей грамматикой, если после замены каждого символа одной из своих категорий полученная последовательность сводится к некоторой целевой.
В данном докладе рассматривается подкласс категориальных грамматик, в которых каждому символу присвоена единственная категория. Это ограничение снижает выразительную мощность формализма (например, язык $a^+$ не может быть порожден). Главная цель – глубже понять, сколько выразительной мощности остается. Можно заметить, что даже если каждому символу назначена уникальная категория, это не означает полное отсутствие неоднозначности; последовательность категорий может иметь разные свертки, потому что все еще существует выбор, откуда в последовательности начать сокращение. Это наблюдение используется для доказательства того, что возможно закодировать любую контекстно-свободную грамматику в категориальную грамматику с единственным назначением категорий таким образом, чтобы слово w принадлежало языку контекстно-свободной грамматики тогда и только тогда, когда его кодирование находится в языке категориальной грамматики. Таким образом, в частности, получается усиление классической теоремы Грейбах о самом трудном языке.
Доклад основан на совместной работе с А.С. Охотиным.
 
  Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024