Алгебраическая характеристика класса частично-рекурсивных графовых функцій

Abstract

Рассмотрен класс вычислимых функций на множестве графов. Определено порождающее множество алгебры частично-рекурсивных функций на новом носителе — графе, а также доказана его полнота.

Розглянуто клас обчислюваних функцій на множині графів. Визначено породжуючу множину алгебри частково-рекурсивних функцій на новому носії — графі, а також доведено її повноту.

The class of all computable functions depending on finite graphs is considered. A generating set for the algebra of partially recursive graph functions is determined, and it is also proved that this set is complete.