Geodesic
Geometric condition of formal grammars solvability
Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 106-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper, we continue the development of a method for studying formal grammars, which means systems of non-commutative polynomial equations. Such systems are solved in the form of formal power series (FPS) that represent non-terminal alphabet characters through terminal alphabet characters; the first component of the solution is a formal language. The method developed by the authors is based on the study of the commutative image of grammar and formal language. Namely, every FPS is associated with its commutative image, which is obtained if we assume that all symbols are commutative variables. A theorem that gives a sufficient geometric condition for the formal grammar to have a unique solution in the form of FPS is obtained: if the commutative images of non-commutative equations of a system define smooth complex analytical hypersurfaces at the point 0, and the normals to them drawn from this point are linearly independent, then the system of non-commutative equations has a unique solution in the form of FPS.
Keywords: systems of polynomial equations, formal power series, commutative image
Mots-clés : non-commutative variables, analytic hypersurface. 
@article{PDMA_2020_13_a30,
     author = {O. I. Egorushkin and I. V. Kolbasina and K. V. Safonov},
     title = {Geometric condition of formal grammars solvability},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {106--108},
     year = {2020},
     number = {13},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2020_13_a30/}
}
TY  - JOUR
AU  - O. I. Egorushkin
AU  - I. V. Kolbasina
AU  - K. V. Safonov
TI  - Geometric condition of formal grammars solvability
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2020
SP  - 106
EP  - 108
IS  - 13
UR  - http://geodesic.mathdoc.fr/item/PDMA_2020_13_a30/
LA  - ru
ID  - PDMA_2020_13_a30
ER  - 
%0 Journal Article
%A O. I. Egorushkin
%A I. V. Kolbasina
%A K. V. Safonov
%T Geometric condition of formal grammars solvability
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2020
%P 106-108
%N 13
%U http://geodesic.mathdoc.fr/item/PDMA_2020_13_a30/
%G ru
%F PDMA_2020_13_a30
O. I. Egorushkin; I. V. Kolbasina; K. V. Safonov. Geometric condition of formal grammars solvability. Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 106-108. http://geodesic.mathdoc.fr/item/PDMA_2020_13_a30/

[1] 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

[2] 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

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

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

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

[6] Safonov K. V., Egorushkin O. I., “O sintaksicheskom analize i probleme V. M. Glushkova raspoznavaniya kontekstno-svobodnykh yazykov Khomskogo”, Vestnik Tomskogo gosuniversiteta. Prilozhenie, 2006, no. 17, 63–67

[7] Safonov K. V., “Ob usloviyakh algebraichnosti i ratsionalnosti summy stepennogo ryada”, Matem. zametki, 41:3 (1987), 325–332 | MR | Zbl

[8] 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