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

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

Prikladnaâ diskretnaâ matematika, no. 3 (2017), pp. 76-89.

Résumé

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.

Détail

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

Bibliographie

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

[2] Glushkov V. M., Tseytlin G. E., Yushchenko E. L., Algebra. Languages. Programming, Naukova dumka, Kiev, 1973, 319 pp. (in Russian) | MR

[3] Griffiths P., Harris J., Principles of Algebraic Geometry, v. 1, John Wiley and Sons, N.Y., 1978, 348 pp. | MR | MR | Zbl

[4] Egorushkin O. I., Kolbasina I. V., Safonov K. V., “On consistency of systems of symbolic polynomial equations and its application”, Prikladnaya Discretnaya Mathematika. Prilozhenie, 2016, no. 9, 119–121 (in Russian)

[5] Egorushkin O. I., Kolbasina I. V., Safonov K. V., “On solvability of systems of symbolic polynomial equations”, J. Siberian Federal University. Mathematics and Physics, 9:2 (2016), 166–172 | MR

[6] Semenov A. L., “Algorithmic problems for power series and context-free grammars”, Doklady Akademii nauk SSSR, 212 (1973), 50–52 (in Russian) | Zbl

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

[8] Safonov K. V., Egorushkin O. I., “Syntactical analysis and the V. M. Glushkov problem of recognition of Chomsky Context-Free Languages”, Vestnik TSU. Prilozhenie, 2006, no. 17, 63–67 (in Russian)

[9] Safonov K. V., “An algebraicity criterion for the sum of a power series (a generalization of Kronecker's criterion) and its application”, Doklady Mathematics, 79:1 (2009), 13–15 | DOI | MR | Zbl

[10] Pemantle R., Wilson M. C., Analytic Combinatorics in Several Variables, Cambridge University Press, Cambridge, 2013, 414 pp. | MR | Zbl

[11] Herve M., Several Complex Variables. Local Theory, Oxford University, Oxford, 1963, 158 pp. | MR | Zbl

[12] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, LAN' Publ., SPb.–Moscow–Krasnodar, 2015, 608 pp. (in Russian)

[13] Aizenberg L. A., Yuzhakov A. P., Integral Representations and Residues in Multidimensional Complex Analysis, Translations of Mathematical Monographs, 58, AMS, Providence, 1983, 283 pp. | MR | Zbl