RUS  ENG
Полная версия
ЖУРНАЛЫ // Интеллектуальные системы. Теория и приложения // Архив

Интеллектуальные системы. Теория и приложения, 2021, том 25, выпуск 4, страницы 129–132 (Mi ista432)

Часть 2. Математика и компьютерные науки

О темпах роста структур с конечным числом существенных ограничений

С. А. Комков

МГУ

Аннотация: Для конечного множества $A$ с заданным на нём множеством операций $M$ определена функция, называемая темпом роста. Порядок роста этой функции характеризует силу и исчислимость множества операций. Показано, что если среди множества всех предикатов, сохраняемых всеми функциями из $M$, встречается лишь конечное число важных существенных предикатов, то темп роста пары $(A, M)$ имеет логарифмический порядок.

Ключевые слова: темп роста, конечные множества, язык ограничений, логарифмический темп роста.



© МИАН, 2024