Open AccessALPHA-MATRIX AND GRAPH-GENERATED GRAMMARS
Author(s) -
В. П. Цветов
Publication year - 2017
Publication title -
vestnik samarskogo universiteta. estestvennonaučnaâ seriâ
Language(s) - English
Resource type - Journals
eISSN - 2712-8954
pISSN - 2541-7525
DOI - 10.18287/2541-7525-2017-23-1-28-40
Subject(s) - tree adjoining grammar , l attributed grammar , phrase structure grammar , combinatorics , mathematics , rule based machine translation , discrete mathematics , indexed grammar , graph rewriting , context free grammar , computer science , graph , artificial intelligence
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.