Заглавие | Monadic second-order logic on equivalence relations |
Вид публикация | Journal Article |
Година на публикуване | 2009 |
Автори | Georgiev G., Tinchev T. |
Списание | Annuaire de l’Université de Sofia “St. Kliment Ohridski”. Faculté de Mathématiques et Informatique |
Том | 99 |
ключови думи | decidability, elimination of second-order quantifiers, equivalence relations, finite model property, MSO sentences |
Резюме | This paper is devoted to exploring expressible power of monadic second-order sentences over the class of all relational structures containing only finite number of equivalence relations which are in local agreement (i.e. for any point of the universe the corresponding equivalence classes with set theoretic inclusion form linear order). Using the pebble games we prove the finite model property and establish an effective translation of these sentences in the first-order language preserving the models. So, the monadic second-order language over the considered class of relational structures has the same expressible power as the first-order language and the monadic second-order theory of this class of structures is decidable. |
2000 MSC | main 03C52, secondary 03C13, 03C85 |
Прикачен файл | Размер |
---|---|
99-025-035.pdf | 982.78 KB |