Альфа-матрицы и граф-порожденные грамматики

В статье рассматривается обобщение граф-порожденных грамматик на основе их матричных представлений. Изучаются два класса граф-порожденных грамматик, связанные с вершинными и реберными разметками порождающих графов. Дается определение альфа-матрицы над полукольцом языков, заданных при помощи конечного алфавита $\mathcal{A}$, и определяются соответствующие матричные алгебры. Введенные понятия в дальнейшем используются для конструктивного представления граф-порожденных языков и исследования вопросов, связанных с их эквивалентностью. Дается определение матрично порожденных грамматик как естественного надкласса граф-порожденных грамматик. Доказываемые утверждения иллюстрируются примерами.