Prikladnaya Diskretnaya Matematika. Supplement
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat. Suppl.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika. Supplement, 2020, Issue 13, Pages 106–108
DOI: https://doi.org/10.17223/2226308X/13/31
(Mi pdma511)
 

Mathematical Foundations of Informatics and Programming

Geometric condition of formal grammars solvability

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

M. F. Reshetnev Siberian State University of Science and Technologies
References:
Abstract: 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, non-commutative variables, formal power series, commutative image, analytic hypersurface.
Document Type: Article
UDC: 519.682
Language: Russian
Citation: O. I. Egorushkin, I. V. Kolbasina, K. V. Safonov, “Geometric condition of formal grammars solvability”, Prikl. Diskr. Mat. Suppl., 2020, no. 13, 106–108
Citation in format AMSBIB
\Bibitem{EgoKolSaf20}
\by O.~I.~Egorushkin, I.~V.~Kolbasina, K.~V.~Safonov
\paper Geometric condition of formal grammars solvability
\jour Prikl. Diskr. Mat. Suppl.
\yr 2020
\issue 13
\pages 106--108
\mathnet{http://mi.mathnet.ru/pdma511}
\crossref{https://doi.org/10.17223/2226308X/13/31}
Linking options:
  • https://www.mathnet.ru/eng/pdma511
  • https://www.mathnet.ru/eng/pdma/y2020/i13/p106
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Prikladnaya Diskretnaya Matematika. Supplement
    Statistics & downloads:
    Abstract page:94
    Full-text PDF :36
    References:15
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024