Теория списков и $\Sigma$-определимость

Списочной алгеброй над некоторым множеством $S$ называется двусортная модель, основное множество которой состоит из множества $S$ и списочной надстройки $I_S$ над множеством $S$ — множества списков элементов из $S \cup I_S$, снабженная естественными отношениями и операциями на списках (отношение принадлежности элемента списку, отношение подсписка, операции взятия головы и хвоста списка, операция присоединения элемента к списку). В данной работе показано, что операции в списочных алгебрах, которые могут быть заданы рекурсивно как по длине так и по глубине списка, являются $\Sigma$-определимыми.