Geodesic
On solving linear homogeneous grammars generating linear languages
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 123-125 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We investigate systems of noncommutative symbolic linear homogeneous equations, which are interpreted as linear grammars of formal languages. Such systems are solved in the form of formal power series (FPS) expressing nonterminal symbols through terminal symbols of the alphabet and considered as linear languages. Each FPS is matched by its commutative image, which is obtained under the assumption that all symbols denote commutative variables, real or complex. In this paper, we consider systems of equations that can have an infinite number of solutions, parameterized not by arbitrary numbers, but by arbitrary FPS. We estimate the number of such parameters, which gives a noncommutative analogue of the well-known fact of the theory of linear equations.
Keywords: systems of linear homogeneous equations, formal power series, commutative image.
Mots-clés : noncommutative variables 
@article{PDMA_2024_17_a29,
     author = {O. I. Egorushkin and I. V. Kolbasina and K. V. Safonov},
     title = {On solving linear homogeneous grammars generating linear languages},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {123--125},
     year = {2024},
     number = {17},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a29/}
}
TY  - JOUR
AU  - O. I. Egorushkin
AU  - I. V. Kolbasina
AU  - K. V. Safonov
TI  - On solving linear homogeneous grammars generating linear languages
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 123
EP  - 125
IS  - 17
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a29/
LA  - ru
ID  - PDMA_2024_17_a29
ER  - 
%0 Journal Article
%A O. I. Egorushkin
%A I. V. Kolbasina
%A K. V. Safonov
%T On solving linear homogeneous grammars generating linear languages
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 123-125
%N 17
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a29/
%G ru
%F PDMA_2024_17_a29
O. I. Egorushkin; I. V. Kolbasina; K. V. Safonov. On solving linear homogeneous grammars generating linear languages. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 123-125. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a29/

[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 | Zbl

[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, 212 (1973), 50–52 | Zbl