RUS  ENG
Full version
JOURNALS // Prikladnaya Diskretnaya Matematika. Supplement // Archive

Prikl. Diskr. Mat. Suppl., 2021 Issue 14, Pages 176–178 (Mi pdma559)

Mathematical Foundations of Informatics and Programming

On a solution of polynomial grammars and the general algebraic equation

O. I. Egorushkin, I. V. Kolbasina, K. V. Safonov

M. F. Reshetnev Siberian State University of Science and Technologies

Abstract: In this paper, we investigate the solvability of formal grammars, by which we mean systems of non-commutative polynomial equations, in the case of one equation. Formal grammars are solved in the form of formal power series (FPS), which express nonterminal symbols of the language through terminal symbols; the first component of the solution is the formal language. The authors develop a method based on the study of the commutative image of grammar and language, which is obtained if in any FPS the symbols of the alphabet are considered commutative variables. A theorem is obtained that gives a power series expansion of the solution to a general algebraic equation, and also allows us to investigate the solvability in the form of an FPS of a polynomial grammar consisting of one equation.

Keywords: general algebraic equation, polynomial grammar, formal power series, non-commutative symbols, commutative image.

UDC: 519.682

DOI: 10.17223/2226308X/14/40



© Steklov Math. Inst. of RAS, 2025