Матричные иерархии языков первого порядка и их приложения

В терминах бесконечных матриц дается определение матричной иерархии языков. Указываются необходимые и достаточные условия рекурсивности и фундированности такой иерархии. Доказано существование фундированной матричной иерархии, представляющей любую рекурсивно-перечислимую степень неразрешимости как степень неразрешимости теории многообразия всех полугрупп. Наконец, дается определение абстрактной иерархии, и находится характеризация абстрактных иерархий как частично упорядоченных множеств.