Реферат: В работе исследуется вопрос моделирования форм Бэкуса-Наура (BNF-систем), а также порождающих грамматик с помощью GNF-систем. GNF-системы являются базой для построения монотонных операторов таких, что наименьшие неподвижные точки этих операторов являются полиномиально вычислимыми. В данной работе результаты, полученные с помощью построения подходящих GNF-систем и применения к ним обобщенного полиномиального аналога теоремы Ганди о неподвижной точке, смогли дать ответы на вопросы существования полиномиально вычислимого представления для множества выводов в порождающих грамматиках. Более того, было показано, что если GNF-система моделирует BNF-систему, то множество прообразов в GNF-системе для множества представлений любого нетерминального символа в BNF-системе также является полиномиально вычислимым. Этот результат сразу позволяет перекодировать все определяемые конструкции в BNF-системе, в том числе синтаксис программ высокоуровневых языков программирования так, что они становятся распознаваемые за полиномиальное время.

Библиографическая ссылка: Нечёсов А.В.
Некоторые вопросы полиномиально вычислимых представлений для порождающих грамматик и форм Бэкуса-Наура
Математические труды. 2022. Т.25. №1. С.134-151. DOI: 10.33048/mattrudy.2022.25.106 РИНЦ

Переводная: Nechesov A.V.
Some Questions on Polynomially Computable Representations for Generating Grammars and Backus–Naur Forms.
Siberian Advances in Mathematics. 2022. V.32. P.299–309. DOI: 10.1134/S1055134422040058 Scopus РИНЦ OpenAlex

Даты:

Поступила в редакцию:	22 февр. 2022 г.
Принята к публикации:	12 мая 2022 г.
Опубликована в печати:	30 июн. 2022 г.
Опубликована online:	30 июн. 2022 г.

Идентификаторы БД:

≡ РИНЦ:

50047164

Альметрики: