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

DOI10.1016/j.tcs.2009.04.019zbMath1171.03005MaRDI QIDQ837190

Christian Mathissen

Publication date: 10 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.04.019

zbMATH Keywords

Ehrenfeucht-Fraïssé game; texts; Ajtai-Fagin game; existential monadic second-order logic; successor structure

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

Related Items

Unnamed Item, Varieties of recognizable tree series over fields, Definable transductions and weighted logics for texts

Cites Work

• T-structures, T-functions, and texts
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Context-free text grammars
• Monadic second-order definable graph transductions: a survey
• Monadic second-order definable text languages
• On monadic NP vs monadic co-NP
• The monadic quantifier alternation hierarchy over grids and graphs
• Weak Second‐Order Arithmetic and Finite Automata
• Reachability is harder for directed than for undirected finite graphs
• Decision Problems of Finite Automata Design and Related Arithmetics
• Monadic generalized spectra
• Definable Transductions and Weighted Logics for Texts
• Algebraic automata and context-free sets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item