Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы

Продолжено изучение выразительной силы языка логики предикатов для конечных алгебраических систем, вложенных в бесконечные, которое было начато в работах М. А. Тайцлина, М. Бенедикта, Л. Либкина и др. Изучено, какие свойства конечной монадической системы можно выразить с помощью формул, если вложить такую систему в линейно упорядоченный произвольным образом случайный граф. Использовано представление Бюхи для связи монадических состояний и формальных языков. Показано, что если ограничиться рассмотрением только $<$-инвариантных в линейно упорядоченных случайных графах формул, то такие формулы соответствуют конечным автоматам. Продемонстрировано, что $=$-инвариантные формулы, выражающие собственные свойства вложенных систем, способны выразить только булеву комбинацию свойств вида “мощность пересечения одноместных предикатов принадлежит одной из конечного числа фиксированных конечных или бесконечных арифметических прогрессий”.
Библиография: 18 наименований.