The decision problem for some logics for finite words on infinite alphabets

Данная статья является продолжением предыдущего исследования авторов, в котором исследовалась логическая характеризация (в духе Эйленберга, Элгота и Шефердсона) $n$-арных синхронных отношений в случае бесконечного алфавита. Показано, что изменение одного из предикатов приводит к совершенно иной картине для бесконечных алфавитов, тогда как для конечных алфавитов выразительная сила остается неизменной. А именно, возможность выразить тот факт, что два слова заканчиваются одним и тем же символом, приводит к неразрешимости уже для $\Sigma_2$-фрагмента теории. Кроме того, доказывается, что $\Sigma_1$-фрагмент разрешим. Библ. – 19 назв.