Geodesic
Alpha-matrix and graph-generated grammars
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 1 (2017), pp. 28-40 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $\mathcal{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.
Keywords: semirings of languages, generative grammars, graph theory, paths in graphs, labeled graphs, graph-generated grammars, matrix-generated grammars.
Mots-clés : formal grammars 
@article{VSGU_2017_1_a3,
     author = {V. P. Tsvetov},
     title = {Alpha-matrix and graph-generated grammars},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {28--40},
     year = {2017},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2017_1_a3/}
}
TY  - JOUR
AU  - V. P. Tsvetov
TI  - Alpha-matrix and graph-generated grammars
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2017
SP  - 28
EP  - 40
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VSGU_2017_1_a3/
LA  - ru
ID  - VSGU_2017_1_a3
ER  - 
%0 Journal Article
%A V. P. Tsvetov
%T Alpha-matrix and graph-generated grammars
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2017
%P 28-40
%N 1
%U http://geodesic.mathdoc.fr/item/VSGU_2017_1_a3/
%G ru
%F VSGU_2017_1_a3
V. P. Tsvetov. Alpha-matrix and graph-generated grammars. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 1 (2017), pp. 28-40. http://geodesic.mathdoc.fr/item/VSGU_2017_1_a3/

[1] Tsvetov V. P., “On a superclass of A-grammars”, Vestnik of Samara State University. Natural Science Series, 2014, no. 10(121), 102–108 (in Russian)

[2] Golan J. S., The Theory of Semirings with Applications in Mathematics and Theoretical Computer Science, Pitman Monographs and Surveys in Pure and Appl. Math., 54, Pitman, 1991 (in English) | MR

[3] Hebisch U., Weinert H. J., Semirings, Algebraic Theory and Applications in Computer Science, World Scientific, Singapore, 1998 (in English) | MR | Zbl

[4] Molchanov V. A., “On matrix semigroups over semirings and their applications to the theory of formal languages”, Mathematics. Mechanics. Collection of Scientific Papers, 3, Izd-vo Sarat. un-ta, Saratov, 2001, 98–101 (in Russian)

[5] Maslov V. P., Kolokoltsov V. N., Idempotent analysis and its application in optimal control, Nauka, M., 1994 (in Russian)

[6] Aleshnikov S. I., Boltnev Yu. F., Ezik Z. et al., “Formal languages and automata I: Conway semirings and finite state machines”, IKBFU's Vestnik, 2003, no. 3, 7–38 (in Russian)

[7] Aleshnikov S. I., Boltnev Yu. F., Ezik Z. et al., “Formal languages and automata II: continuous semirings and algebraic systems”, IKBFU's Vestnik, 2005, no. 1–2, 19–45 (in Russian)

[8] Ismagilov R. S., Mastikhina A. A., “On the problem of partial guessing of formal languages”, Herald of the Bauman Moscow State Technical University, Series Natural Sciences, 2016, no. 2, 3–15 (in Russian) | DOI

[9] Biserov D. S., Igudesman K. B., “Matrices over the semiring of binary relations and V-component fractals”, Russian Mathematics (Iz. VUZ), 2011, no. 5, 75–79 (in Russian)

[10] Tsvetov V. P., “On a special restriction of reflexive and symmetric relation to an equivalence relation”, Vestnik of Samara State University. Natural Science Series, 2006, no. 4(44), 26–47 (in Russian)