|
|
Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
1 марта 2021 г. 18:30, г. Москва, МИАН (ул. Губкина, 8), ауд. 313 + Zoom
|
|
|
|
|
|
Базовые категориальные грамматики с однозначным присвоением типов
М. Е. Вишникин |
Количество просмотров: |
Эта страница: | 105 |
|
Аннотация:
Понятие базовой категориальной грамматики (БКГ) восходит к работам Айдукевича (1934) и Бар-Хиллела (1953). В БКГ каждая буква алфавита сопоставляется нескольким типам (категориям), а слово принадлежит языку, если хотя бы для одного выбора этих типов выводима соответствующая секвенция. Известно, что для любой контекстно-свободной грамматики существует БКГ, задающая тот же язык (возможно, за вычетом пустого слова). Верно и обратное.
В основной части доклада планируется рассмотреть результаты связанные с определением автоматности языка заданного БКГ с однозначным присвоением типов. Будут доказаны необходимые условия автоматности языка. Также планируется рассмотреть связь между графом (который можно построить по БКГ) и необходимыми условиями автоматности.
|
|