Эта публикация цитируется в
5 статьях
Монадические состояния над упорядоченным универсальным случайным графом и конечные автоматы
С. М. Дудаков Тверской государственный университет
Аннотация:
Продолжено изучение выразительной силы языка логики предикатов для конечных алгебраических систем, вложенных в бесконечные, которое было начато в работах М. А. Тайцлина, М. Бенедикта, Л. Либкина и др. Изучено, какие свойства конечной монадической системы можно выразить с помощью формул, если вложить такую систему в линейно упорядоченный произвольным образом случайный граф. Использовано представление Бюхи для связи монадических состояний и формальных языков. Показано, что если ограничиться рассмотрением только
$<$-инвариантных в линейно упорядоченных случайных графах формул, то такие формулы соответствуют конечным автоматам. Продемонстрировано, что
$=$-инвариантные формулы, выражающие собственные свойства вложенных систем, способны выразить только булеву комбинацию свойств вида “мощность пересечения одноместных предикатов принадлежит одной из конечного числа фиксированных конечных или бесконечных арифметических прогрессий”.
Библиография: 18 наименований.
Ключевые слова:
универсальный случайный граф, логика первого порядка, автоматный язык.
УДК:
510.62
MSC: Primary
05C80; Secondary
08A70,
11B85,
68P15 Поступило в редакцию: 15.01.2009
DOI:
10.4213/im4077