Email this article 
ALPHA-MATRIX AND GRAPH-GENERATED GRAMMARS
- Authors: Tsvetov V.P.1
-
Affiliations:
- Samara National Research University
- Issue: Vol 23, No 1 (2017)
- Pages: 28-40
- Section: Articles
- URL: https://journals.ssau.ru/est/article/view/5144
- DOI: https://doi.org/10.18287/2541-7525-2017-23-1-28-40
- ID: 5144
Cite item
Full Text
Abstract
In this paper we consider the extension of graph-generated grammars based on their matrix representations. We study two classes of graph-generated grammars associated with the vertex and edge marking of graphs. We define alpha-matrices over a semiring of languages specified by finite alphabet A and then define the corresponding matrix algebras. These concepts are then used for constructive representation of graph-generated languages and research of their equivalence. We define a matrix-generated grammars as a natural superclass of graph-generated grammars. All the proofs are illustrated by examples.
About the authors
V. P. Tsvetov
Samara National Research University
Author for correspondence.
Email: morenov@ssau.ru
Russian Federation
References
- Tsvetov V.P. Ob odnom nadklasse A-grammatik . Vestnik Samarskogo gosudarstvennogo universiteta. Estestvennonauchnaia seriia , 2014, no. 10(121), pp. 102–108 .
- Golan J.S. The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science. Pitman, 1991. (Pitman Monographs and Surveys in Pure and Appl. Math.; Vol. 54) .
- Hebisch U., Weinert H.J. Semirings. Algebraic Theory and Applications in Computer Science. Singapore: World Scientific, 1998 .
- Molchanov V.A. O matrichnykh polugruppakh nad polukol’tsami i ikh prilozheniia k teorii formal’nykh iazykov . Matematika. Mekhanika. Sbornik nauchykh trudov. Vyp. . Saratov: Izd-vo Sarat. un-ta, 2001, pp. 98–101 .
- Maslov V.P., Kolokoltsov V.N. Idempotentnyi analiz i ego primenenie v optimal’nom upravlenii . M.: Nauka, 1994 .
- Aleshnikov S.I., Boltnev Yu.F., Ezik Z. et al. Formal’nye iazyki i avtomaty I: polukol’tsa Konveia i konechnye avtomaty . Vestnik Kaliningradskogo gosudarstvennogo universiteta , 2003, Issue 3, pp. 7–38 .
- Aleshnikov S.I., Boltnev Yu.F., Ezik Z. et al. Formal’nye iazyki i avtomaty II: nepreryvnye polukol’tsa i algebraicheskie sistemy . Vestnik Kaliningradskogo gosudarstvennogo universiteta , 2003, Issue 1–2, pp. 19–45 .
- Ismagilov R.S., Mastikhina A.A. K voprosu chastichnogo ugadyvaniia formal’nykh iazykov . Vestnik MGTU im. N.E. Baumana. Ser. Estestvennye nauki , 2016, no. 2, pp. 3-–15. doi: 10.18698/1812-3368-2016-2-3-15 .
- Biserov D.S., Igudesman K.B. Matritsy nad polukol’tsom binarnykh otnoshenii i V-komponentnye fraktaly . Izv. vuzov. Matem. , 2011, no. 5, pp. 75–79 .
- Tsvetov V.P. O spetsial’nom suzhenii konechnogo refleksivnogo simmetrichnogo otnosheniia do otnosheniia ekvivalentnosti . Vestnik Samarskogo gosudarstvennogo universiteta. Estestvennonauchnaia seriia , 2006, no. 4(44), pp. 26–47 .
Supplementary files
