Some Questions on Polynomially Computable Representations for Generating Grammars and Backus–Naur Forms. | Sciact - Система учета научной деятельности ИМ СО РАН

Some Questions on Polynomially Computable Representations for Generating Grammars and Backus–Naur Forms. Научная публикация

Журнал

Siberian Advances in Mathematics
ISSN: 1055-1344 , E-ISSN: 1934-8126

Вых. Данные

Год: 2022, Том: 32, Страницы: 299–309 Страниц : 11 DOI: 10.1134/S1055134422040058

Ключевые слова

gandy's theorem, polynomial computability, bnf systems, generative grammar

Авторы

Nechesov A.V. ¹

Организации

1	Sobolev Institute of Mathematics

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0011

In the present article, we consider the question on modeling Backus–Naur forms (BNF-systems) and generating grammars in GNF-systems. GNF-systems serve as the base for construction of monotone operators whose least ﬁxed points are polynomially computable. We obtain our results by construction of GNF-systems and application of a generalized polynomial analogue of the Gandy’s ﬁxed point theorem. This allows us to answer some questions on existence of a polynomially computable representation for the set of derivations in generating grammars. Moreover, we show that, for each GNF-system modeling a BNF-system and every nonterminal symbol in the BNF-system, the set of preimages in the GNF-system of representations of this symbol is polynomially computable. This result allows us to encode all deﬁnable constructions of the BNF-system, including the syntax of programs in high-level programming languages, so that they become recognizable in polynomial time

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

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

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

≡ Scopus:	2-s2.0-85144136477
≡ РИНЦ:	58957245
≡ OpenAlex:	W4311897128