RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



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






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


Prikl. Diskr. Mat., 2017, Number 37, Pages 76–89 (Mi pdm590)  

This article is cited in 1 scientific paper (total in 1 paper)

Mathematical Foundations of Informatics and Programming

On application of multidimensional complex analysis in formal language and grammar theory

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

Reshetnev State University of Science and Technology, Krasnoyarsk, Russia

Abstract: Systems of polynomial equations over a semiring (with respect to symbols with a non-commutative multiplication and a commutative addition) are investigated. These systems of equations are interpreted as the grammars of formal languages and are resolved with respect to the non-terminal symbols in the form of the formal power series (FPS) depending on the terminal symbols. The commutative image of the system of equations is determined under the assumption that the symbols are variables taking values from the field of complex numbers. The connections between solutions of the non-commutative symbolic system of equations and its commutative image are established, thus the methods for multidimensional complex analysis are involved in the theory of formal language grammars. A discrete analogue of implicit mapping theorem onto formal grammars is proved: a sufficient condition for the existence and the uniqueness of a solution of a non-commutative system of equations in the form of FPS is the inequality to zero of the Jacobian of the commutative image of this system. A new method for syntactic analysis of the monomials of a context-free language as a model of programming languages is also proposed. The method is based on the integral representation of the syntactic polynomial of a program. It is shown that the integral of a fixed multiplicity over a cycle allows finding the syntactic polynomial of a monomial (program) with the unlimited number of symbols, that gives a new approach to the problem of syntactic analysis.

Keywords: formal power series, commutative image, syntactic analysis, integral representation.

Funding Agency Grant Number
Russian Foundation for Basic Research 17-47-240318


DOI: https://doi.org/10.17223/20710410/37/6

Full text: PDF file (702 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.682

Citation: O. I. Egorushkin, I. V. Kolbasina, K. V. Safonov, “On application of multidimensional complex analysis in formal language and grammar theory”, Prikl. Diskr. Mat., 2017, no. 37, 76–89

Citation in format AMSBIB
\Bibitem{EgoKolSaf17}
\by O.~I.~Egorushkin, I.~V.~Kolbasina, K.~V.~Safonov
\paper On application of multidimensional complex analysis in formal language and grammar theory
\jour Prikl. Diskr. Mat.
\yr 2017
\issue 37
\pages 76--89
\mathnet{http://mi.mathnet.ru/pdm590}
\crossref{https://doi.org/10.17223/20710410/37/6}


Linking options:
  • http://mi.mathnet.ru/eng/pdm590
  • http://mi.mathnet.ru/eng/pdm/y2017/i3/p76

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. R. V. Ul'vert, “On Computability of Multiple Integrals By Means of a Sum of Local Residues”, Sib. Electron. Math. Rep., 15 (2018), 996–1010  mathnet  mathnet  crossref  mathscinet  zmath  isi
  • Прикладная дискретная математика
    Number of views:
    This page:228
    Full text:92
    References:25

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021