Existential MSO over two successors is strictly weaker than over linear orders
From MaRDI portal
Publication:837190
DOI10.1016/j.tcs.2009.04.019zbMath1171.03005MaRDI QIDQ837190
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
Ehrenfeucht-Fraïssé game; texts; Ajtai-Fagin game; existential monadic second-order logic; successor structure
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
Related Items
A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic., 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