Abstract:
Объектом исследования данной работы является свойство конечности конечно-определенных систем, задаваемых с помощью набора квазитождеств. Цель работы заключается в выявлении тех конкретных случаев, когда существует алгоритм, определяющий конечность таких систем. В исследовании применяются методы теории алгоритмов. Использованы результаты предыдущих исследований (С. И. Адян, В.Ю. Попов) в смежных областях (алгоритмических свойств конечно-определенных полугрупп и групп). Получены следующие результаты: в сигнатуре c одной унарной операцией и константами существует единый алгоритм, распознающий конечность свободных систем; в сигнатуре с одной бинарной операцией и хотя бы одной константой, так же как в сигнатуре с несколькими (n + 1)-арными операциями не существует общего алгоритма.
Результаты данной работы могут быть применены в исследовании корректности описания
абстрактных типов данных с помощью квазитождеств.
