کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435517 689911 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Existential MSO over two successors is strictly weaker than over linear orders
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Existential MSO over two successors is strictly weaker than over linear orders
چکیده انگلیسی

As is well known, a language of finite words, considered as labeled linear orders, is definable in monadic second-order logic (MSO) iff it is definable in the existential fragment of MSO, that is the quantifier alternation hierarchy collapses. Even more, it does not make a difference if we consider existential MSO over a linear order or a successor relation only. In this note we show that somewhat surprisingly the latter does not hold if we just add a second linear order and consider finite relational structures with two linear orders, so-called texts.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 410, Issues 38–40, 6 September 2009, Pages 3982-3987