О разрешимости списочных структур

Изучается теоретико-вычислимая сложность различных структур, основанных на списочном типе данных. Списочная надстройка над структурой $S$ содержит два сорта элементов: атомы из $S$ и конечные линейные списки атомов. Сигнатура списочной надстройки состоит из сигнатуры $S$, пустого списка $nil$ и бинарной операции присоединения атома к списку. Обогащенная списочная надстройка над $S$ получается добавлением к сигнатуре дополнительных функций и отношений: взятия последнего элемента списка, получения остатка списка после удаления последнего элемента, отношения принадлежности атома к списку и отношения «быть начальным сегментом списка».
Доказано, что элементарная теория обогащенной списочной надстройки над $(\omega, +)$, т. е. моноида натуральных чисел относительно сложения, вычислимо изоморфна арифметике первого порядка. В частности, это означает, что преобразование структуры $S$ в обогащенную списочную надстройку над $S$ не всегда сохраняет разрешимость элементарных теорий. Также показано, что списочная надстройка над $S$ может быть представлена с помощью конечного автомата в том и только том случае, когда $S$ конечна.