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

DOI10.1016/j.tcs.2009.04.019zbMath1171.03005OpenAlexW2141383569MaRDI 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é gametextsAjtai-Fagin gameexistential monadic second-order logicsuccessor structure

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (3)

Definable transductions and weighted logics for texts ⋮ Varieties of recognizable tree series over fields ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.

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

This page was built for publication: Existential MSO over two successors is strictly weaker than over linear orders