Некоторые вопросы полиномиально вычислимых представлений для порождающих грамматик и форм Бэкуса – Наура

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