Expressing cardinality quantifiers in monadic second-order logic over trees

DOI10.3233/FI-2010-260MaRDI QIDQ3065008zbMATH OpenOpenAlexFDO

Authors Vince Bárány, Łukasz Kaiser, Alex Rabinovich

Publication date 3 January 2011

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2010-260

zbMATH Keywords

Cantor topologycardinality quantifiersinfinite treesmonadic second-order logic

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Descriptive set theory (03E15) Continuum hypothesis and Martin's axiom (03E50)

Recommendations

• Cardinality Quantifiers in MLO over Trees
• Expressing cardinality quantifiers in monadic second-order logic over chains
• Monadic Second Order Logic with Measure and Category Quantifiers
• Monadic second order finite satisfiability and unbounded tree-width
• An Extension of Muchnik's Theorem

Cited in

(15)

• Counting on CTL^*: On the expressive power of monadic path logic
• Existential monadic second order logic on random rooted trees
• Graded modalities in strategy logic
• On degrees of ambiguity for Büchi tree automata
• Expressing cardinality quantifiers in monadic second-order logic over chains
• Cardinality Quantifiers in MLO over Trees
• Cardinality logics. Part II: Definability in languages based on ‘exactly’
• scientific article; zbMATH DE number 1138595 (Why is no real title available?)
• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• scientific article; zbMATH DE number 7559451 (Why is no real title available?)
• Ambiguity hierarchy of regular infinite tree languages
• Degrees of ambiguity for parity tree automata
• A dichotomy theorem for ordinal ranks in MSO
• Counting branches in trees using games
• A dichotomy theorem for ordinal ranks in MSO

This page was built for publication: Expressing cardinality quantifiers in monadic second-order logic over trees

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