Автоматные структуры и их обобщения

Автоматные структуры - это такие структуры, база которых является регулярным языком,а также каждое отношение которого можно сформулировать через конечные автоматы. Такие структуры удобны тем, что обладают полезными вычислительными свойствами. Про автоматные линейные порядки, частный случай автоматных структур, мы знаем ограничение сверху в терминах конденсируемости. Конденсацией называют переход от одного линейного порядка к другому, не более сложному, объединяющий интервалы, в которых между любыми двумя эле-ментами конечное число элементов, в один элемент. Если порядок не может прийти за конечное число применений такой операции в неизменяемый вид, то такой порядок не является автоматным. В то же время известно, что существуют порядки, сжимающиеся всего за две итерации,но уже не являющиеся автоматными. Задача данной работы исследовать порядки такого вида и выявить, какие ограничения на автоматность существуют для таких, достаточно простых в терминах конденсируемости структур.В первой части мы познакомим с понятием конечного автомата, математической структуры и покажем, когда структура является автоматной. В конце первой части мы покажем главное техническое средство автоматных функций теоремами 5 и 6: разрешимость элементарной теории для автоматных структур и возможность пополнить теорию дополнительным предикатом"существует бесконечно много"с сохранением разрешимости.Во второй части мы познакомим с классическим способом ранжирования линейных порядков, кратко приведем уже известные результаты для автоматных линейных порядков, а затем разберем, что удалось получить про порядки ранга 2.