Abstract: 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 fixed points are polynomially computable. We obtain our results by construction of GNF-systems and application of a generalized polynomial analogue of the Gandy’s fixed 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 definable constructions of the BNF-system, including the syntax of programs in high-level programming languages, so that they become recognizable in polynomial time

Cite: 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

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

Dates:

Submitted:	Feb 22, 2022
Accepted:	Apr 11, 2022
Published print:	May 12, 2022
Published online:	Dec 16, 2022

Identifiers:

≡ Scopus:	2-s2.0-85144136477
≡ Elibrary:	58957245
≡ OpenAlex:	W4311897128

Altmetrics: