کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
11001896 | 1342646 | 2019 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Existential monadic second order logic on random rooted trees
ترجمه فارسی عنوان
منطق مرتبه دوم مسیحی وجود دارد درختان تصادفی ریشه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
گالتون درخت واتسون، محدودیت درخت، خواص دوم مرتبه انحصاری، تقریبا مطمئن بودن واکنش،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We address questions of logic and expressibility in the context of random rooted trees. Infiniteness of a rooted tree is not expressible as a first order sentence, but is expressible as an existential monadic second order sentence (EMSO). On the other hand, finiteness is not expressible as an EMSO. For a broad class of random tree models, including Galton-Watson trees with offspring distributions that have full support, we prove the stronger statement that finiteness does not agree up to a null set with any EMSO. We construct a finite tree and a non-null set of infinite trees that cannot be distinguished from each other by any EMSO of given parameters. This is proved via set-pebble Ehrenfeucht games (where an initial colouring round is followed by a given number of pebble rounds).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 342, Issue 1, January 2019, Pages 152-167
Journal: Discrete Mathematics - Volume 342, Issue 1, January 2019, Pages 152-167
نویسندگان
Alexander E. Holroyd, Avi Levy, Moumanti Podder, Joel Spencer,