Geodesic
On a solution of polynomial grammars and the general algebraic equation
Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 176-178 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, formal power series, non-commutative symbols, commutative image.
Mots-clés : polynomial grammar 
@article{PDMA_2021_14_a40,
     author = {O. I. Egorushkin and I. V. Kolbasina and K. V. Safonov},
     title = {On a solution of polynomial grammars and the general algebraic equation},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {176--178},
     year = {2021},
     number = {14},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2021_14_a40/}
}
TY  - JOUR
AU  - O. I. Egorushkin
AU  - I. V. Kolbasina
AU  - K. V. Safonov
TI  - On a solution of polynomial grammars and the general algebraic equation
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2021
SP  - 176
EP  - 178
IS  - 14
UR  - http://geodesic.mathdoc.fr/item/PDMA_2021_14_a40/
LA  - ru
ID  - PDMA_2021_14_a40
ER  - 
%0 Journal Article
%A O. I. Egorushkin
%A I. V. Kolbasina
%A K. V. Safonov
%T On a solution of polynomial grammars and the general algebraic equation
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2021
%P 176-178
%N 14
%U http://geodesic.mathdoc.fr/item/PDMA_2021_14_a40/
%G ru
%F PDMA_2021_14_a40
O. I. Egorushkin; I. V. Kolbasina; K. V. Safonov. On a solution of polynomial grammars and the general algebraic equation. Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 176-178. http://geodesic.mathdoc.fr/item/PDMA_2021_14_a40/

[1] Glushkov V. M., Tseitlin G. E., Yuschenko E. L., Algebra. Yazyki. Programmirovanie, Naukova dumka, Kiev, 1973 | MR

[2] Salomaa A., Soitolla M., Automata-Theoretic Aspects of Formal Power Series, Springer Verlag, N.Y., 1978 | MR | Zbl

[3] Egorushkin O. I., Kolbasina I. V., Safonov K. V., “O sovmestnosti sistem simvolnykh polinomialnykh uravnenii i ikh prilozhenii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2016, no. 9, 119–121

[4] Egorushkin O. I., Kolbasina I. V., Safonov K. V., “On solvability of systems of symbolic polynomial equations”, Zhurn. SFU. Ser. Matem. i fiz., 9:2 (2016), 166–172 | MR | Zbl

[5] Semenov A. L., “Algoritmicheskie problemy dlya stepennykh ryadov i kontekstno-svobodnykh grammatik”, Dokl. AN SSSR, 212 (1973), 50–52 | Zbl

[6] Safonov K. V., “On power series of algebraic and rational functions in $C^{n}$”, J. Math. Analysis Appl., 243 (2000), 261–277 | DOI | MR | Zbl