Existential MSO over two successors is strictly weaker than over linear orders
type: Item
instance of: scholarly article
title: Existential MSO over two successors is strictly weaker than over linear orders
zbMATH Open document ID: 1171.03005
author: Christian Mathissen
published in: Theoretical Computer Science
publication date: 2009-09-10T00:00:00Z
Mathematics Subject Classification ID: 03B15
Mathematics Subject Classification ID: 03D05
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5602755
zbMATH Keywords: existential monadic second-order logic
zbMATH Keywords: Ehrenfeucht-Fraïssé game
zbMATH Keywords: Ajtai-Fagin game
zbMATH Keywords: texts
zbMATH Keywords: successor structure
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.04.019
OpenAlex ID: W2141383569
cites work: Reachability is harder for directed than for undirected finite graphs
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Monadic second-order definable graph transductions: a survey
cites work: Q4492680
cites work: Decision Problems of Finite Automata Design and Related Arithmetics
cites work: Q4654639
cites work: Theory of 2-structures. I: Clans, basic subclasses, and morphisms
cites work: T-structures, T-functions, and texts
cites work: Context-free text grammars
cites work: Monadic generalized spectra
cites work: Q4353557
cites work: On monadic NP vs monadic co-NP
cites work: Q5551141
cites work: Q4874660
cites work: Monadic second-order definable text languages
cites work: Definable Transductions and Weighted Logics for Texts
cites work: Q3683903
cites work: The monadic quantifier alternation hierarchy over grids and graphs
cites work: Algebraic automata and context-free sets
cites work: Q4714446
cites work: Q4036584
DOI: 10.1016/J.TCS.2009.04.019
description: scientific article; zbMATH DE number 5602755