کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4661829 1633457 2015 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Second-order propositional modal logic and monadic alternation hierarchies
ترجمه فارسی عنوان
منطق مدال گزاره ای دوم مرتبه دوم و سلسله مراتب متناوب مونادی
کلمات کلیدی
منطق مودال؛ کمیت سنج گزاره ای؛ منطق مرتبه دوم مونادی؛ سلسله مراتب متناوب؛ منطق مرتبه دوم
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

We establish that the quantifier alternation hierarchy of formulae of second-order propositional modal logic (SOPML) induces an infinite corresponding semantic hierarchy over the class of finite directed graphs. This solves an open problem of van Benthem (1985) [5] and ten Cate (2006) [11]. We also identify modal characterizations of the expressive power of second-order logic (SO) and monadic second-order logic (MSO) in terms of extensions of modal logic with second-order quantification.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 166, Issue 1, January 2015, Pages 1–28
نویسندگان
,