Geodesic
On a superclass of A-grammars
Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 10 (2014), pp. 102-108 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

In this paper we consider a superclass of automaton grammars that can be represented in terms of paths on graphs. With this approach, we assume that vertices of graph are labeled by symbols of finite alphabet $\mathcal{A}$. We will call such grammars graph-generated grammars or $\mathrm{G}$-grammars. In contrast to the graph grammars that are used to describe graph structure transformations, $\mathrm{G}$-grammars using a graphs as a means of representing formal languages. We will give an algorithm for constructing $\mathrm{G}$-grammar which generate the language recognized by deterministic finite automaton. Moreover, we will show that the class of languages generated by $\mathrm{G}$-grammars is a proper superset of regular languages.
Keywords: formal languages, generative grammars, automata theory, graph theory, paths in graphs, labeled graphs, graph-generated grammars.
Mots-clés : formal grammars 
@article{VSGU_2014_10_a10,
     author = {V. P. Tsvetov},
     title = {On a superclass of {A-grammars}},
     journal = {Vestnik Samarskogo universiteta. Estestvennonau\v{c}na\^a seri\^a},
     pages = {102--108},
     year = {2014},
     number = {10},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VSGU_2014_10_a10/}
}
TY  - JOUR
AU  - V. P. Tsvetov
TI  - On a superclass of A-grammars
JO  - Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
PY  - 2014
SP  - 102
EP  - 108
IS  - 10
UR  - http://geodesic.mathdoc.fr/item/VSGU_2014_10_a10/
LA  - ru
ID  - VSGU_2014_10_a10
ER  - 
%0 Journal Article
%A V. P. Tsvetov
%T On a superclass of A-grammars
%J Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ
%D 2014
%P 102-108
%N 10
%U http://geodesic.mathdoc.fr/item/VSGU_2014_10_a10/
%G ru
%F VSGU_2014_10_a10
V. P. Tsvetov. On a superclass of A-grammars. Vestnik Samarskogo universiteta. Estestvennonaučnaâ seriâ, no. 10 (2014), pp. 102-108. http://geodesic.mathdoc.fr/item/VSGU_2014_10_a10/

[1] Chomsky N., “On certain formal properties of grammars”, Cybernetic collected book, 1962, no. 5, 279–311 (in Russian) | Zbl

[2] Chomsky N. A., “Note on phrase-structure grammar”, Cybernetic collected book, 1962, no. 5, 312–316 (in Russian)

[3] Chomsky N., “Formal properties of grammars”, Cybernetic collected book, new series, 1966, no. 2, 121–230 (in Russian)

[4] Glushkov V. M., “Abstract theory of automata”, Achievements of mathematical sciences, 16:5 (1961), 3–62 (in Russian) | MR | Zbl

[5] Glushkov V. M., “Automata theory and design issues of structures of digital machines”, Cybernetics, 1965, no. 1, 3–11 (in Russian) | MR

[6] Glushkov V. M., “Automata theory and formal microprogram transformations”, Cybernetics, 1:5 (1–9), 1965 (in Russian)

[7] Petrov S. V., “Graph grammars and automata (survey)”, Automatics and Teleautomatics, 1978, no. 7, 116–136 (in Russian)

[8] Balasubramanian D., Narayanan A., Buskirk C. P. et al., “The Graph Rewriting and Transformation Language: GReAT”, Electronic Communications of the EASST, 1 (2006), 1–8 | Zbl

[9] Pfaltz J., Rosenfeld A., “Web Grammars”, Proceedings of the 1st International Joint Conference on Artificial Intelligence (1969), 609–620

[10] Rekers J., Schuerr A., “A Graph Grammar approach to Graphical Parsing”, Proceedings of the 11th IEEE International Symposium (1995), 195–202