Existential MSO over two successors is strictly weaker than over linear orders

详细信息    查看全文

• 作者：Christian Mathissen
• 关键词：Existential monadic second-order logic ; Ehrenfeucht– ; Fraï ; ssé ; game ; Ajtai– ; Fagin game ; Texts ; Successor structure
• 刊名：Theoretical Computer Science
• 出版年：2009
• 出版时间：6 September 2009
• 年：2009
• 卷：410
• 期：38-40
• 页码：3982-3987
• 全文大小：569 K

文摘

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.