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

DOI10.1016/J.TCS.2009.04.019MaRDI QIDQ837190zbMATH OpenOpenAlexFDO

Authors 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

Ajtai-Fagin gameEhrenfeucht-Fraïssé gameexistential monadic second-order logicsuccessor structuretexts

Mathematics Subject Classification ID

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

Recommendations

• Existential second-order logic over strings
• scientific article; zbMATH DE number 2079025
• MSO definable text languages
• Order-invariant MSO is stronger than counting MSO in the finite
• Two-Variable Logic over Countable Linear Orderings

Cites work

• Algebraic automata and context-free sets
• Context-free text grammars
• Decision Problems of Finite Automata Design and Related Arithmetics
• Definable Transductions and Weighted Logics for Texts
• scientific article; zbMATH DE number 3906240 (Why is no real title available?)
• scientific article; zbMATH DE number 176754 (Why is no real title available?)
• scientific article; zbMATH DE number 1059242 (Why is no real title available?)
• scientific article; zbMATH DE number 1478125 (Why is no real title available?)
• scientific article; zbMATH DE number 2143010 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 871246 (Why is no real title available?)
• scientific article; zbMATH DE number 3266604 (Why is no real title available?)
• Monadic generalized spectra
• Monadic second-order definable graph transductions: a survey
• Monadic second-order definable text languages
• On monadic NP vs monadic co-NP
• Reachability is harder for directed than for undirected finite graphs
• T-structures, T-functions, and texts
• The monadic quantifier alternation hierarchy over grids and graphs
• Theory of 2-structures. I: Clans, basic subclasses, and morphisms
• Weak Second‐Order Arithmetic and Finite Automata

Cited in

(4)

• Existential second-order logic over strings
• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• Varieties of recognizable tree series over fields
• Definable transductions and weighted logics for texts

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q837190)