RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Межкафедральный семинар МФТИ по дискретной математике
6 декабря 2017 г. 18:30, г. Долгопрудный, МФТИ, Корпус Прикладной Математики, 115
 


FO and EMSO logic of rooted trees and graphs

М. Е. Жуковский

Количество просмотров:
Эта страница:38

Аннотация: Monadic second order sentence about a finite structure is a formal sentence with quantification over first order variables (elements of the structure) and sets of elements. In existential sentences (EMSO), only existential quantifiers over set variables are allowed. The first part of the talk is devoted to logic of rooted trees. First, we consider Galton-Watson (GW) tree with Poisson(λ) offspring distribution, though most of the results can be extended to very general distributions. We give a complete description of the probabilities Pλ[A] of all possible first order (FO) sentences A conditioned on the survival of the GW tree. Second, we consider the problem of expressing finiteness of a rooted tree in EMSO and prove that it is not expressible (in contrast, infiniteness is expressible in EMSO). We also solve this problem for GW trees. The second part of the talk is devoted to FO and EMSO logic of graphs. It is very well known that, for every first order sentences, it is either true for almost all graphs or false for almost all graphs. In contrast, such a “zero-one law” fails for EMSO. We study quantifier complexities of EMSO sentences without zero-one law. Joint work with Joel Spencer, Alexander Holroyd, Avi Levy.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020