The monadic theory of order

DOI10.2307/1971037zbMATH Open0345.02034OpenAlexW2062792526WikidataQ105487999 ScholiaQ105487999MaRDI QIDQ1233019FDOQ1233019

Authors: S. Shelah 

Publication date: 1975

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/1971037

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Model-theoretic algebra (03C60) Decidability of theories and sets of sentences (03B25)

Cited In (only showing first 100 items - show all)

• Trees, grids, and MSO decidability: from graphs to matroids
• The logical strength of Büchi's decidability theorem
• Logical aspects of Cayley-graphs: the group case
• Notes on monadic logic. Part B: Complexity of linear orders in ZFC
• A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS
• The structure of the models of decidable monadic theories of graphs
• The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates
• Recognizability, hypergraph operations, and logical types
• The monadic theory and the next world
• Monadic logic and Löwenheim numbers
• The complete finitely axiomatized theories of order are dense
• Uniformization and skolem functions in the class of trees
• Convex decompositions in the plane and continuous pair colorings of the irrationals
• Algorithmic uses of the Feferman-Vaught theorem
• The expressive power of Malitz quantifiers for linear orderings
• Continuous time temporal logic with counting
• Temporal logics over linear time domains are in PSPACE
• The spectrum problem for abelian \(\ell\)-groups and MV-algebras
• The decision problem for branching time logic
• Automata on linear orderings
• On frontiers of regular trees
• Decidable metric logics
• On decidability properties of local sentences
• Selection in the monadic theory of a countable ordinal
• On translations of temporal logic of actions into monadic second-order logic
• Towards a language theory for infinite N-free pomsets.
• A weak generalization of MA to higher cardinals
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• Substance and first-order quantification over individual-concepts
• Timer formulas and decidable metric temporal logic
• Monadic second-order logic on tree-like structures
• Taxonomies of model-theoretically defined topological properties
• The full binary tree cannot be interpreted in a chain
• Stationary Logic and Ordinals
• Interpreting second-order logic in the monadic theory of order
• On the Ehrenfeucht-Fraïssé game in theoretical computer science (extended abstract)
• MSOL partitioning problems on graphs of bounded treewidth and clique-width
• A note on edge colorings and trees
• Reflecting stationary sets
• Modest theory of short chains. II
• Time-Bounded Verification
• Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey
• Toward classifying unstable theories
• On the strength of the interpretation method
• Propositional quantification in the topological semantics for \(\mathbf S4\)
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• A syntactic congruence for languages of birooted trees
• The recognizability of sets of graphs is a robust property
• Logic and rational languages of words indexed by linear orderings
• State-strategies for games in F_σδ ∩ G_δσ
• Decidable Extensions of Church’s Problem
• Automata and logics over finitely varying functions
• Selection over classes of ordinals expanded by monadic predicates
• CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS
• Linear Recurrence Relations for Graph Polynomials
• Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings
• Rabin's uniformization problem
• Notes on monadic logic. A: Monadic theory of the real line
• Monadic second-order logic, graph coverings and unfoldings of transition systems
• More on monadic logic. C: Monadically interpreting in stable unsuperstable \(\mathcal T\) and the monadic theory of \(^{\omega}\lambda\)
• New proof of the solvability of the elementary theory of linearly ordered sets
• Weakly maximal decidable structures
• Arity hierarchy for temporal logics
• Monadic theory of order and topology, I
• Modest theory of short chains. I
• On decidability of monadic logic of order over the naturals extended by monadic predicates
• Stationary logic of ordinals
• The monadic second-order logic of graphs. IV: Definability properties of equational graphs
• The expressive power of second-order propositional modal logic
• THE COLORING OF THE TREE OF COLORINGS
• On infinite transition graphs having a decidable monadic theory
• Monadic theory of order and topology. II
• Counting finite models
• Uniformization, choice functions and well orders in the class of trees
• Recursion schemes and the WMSO+U logic
• Infinite and bi-infinite words with decidable monadic theories
• A Hierarchy of Automaticω-Words having a Decidable MSO Theory
• On the Weihrauch degree of the additive Ramsey theorem over the rationals
• Some extensions to propositional mean-value calculus: expressiveness and decidability
• Compositional failure detection in structured transition systems
• Title not available (Why is that?)
• Counting on CTL\(^*\): On the expressive power of monadic path logic
• Title not available (Why is that?)
• A strategy for dynamic programs: start over and muddle through
• Cardinality Quantifiers in MLO over Trees
• Monadic theory of a linear order versus the theory of its subsets with the lifted min/max operations
• Shelah-Stupp's and Muchnik's iterations revisited
• The factorisation forest theorem
• Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
• COMPOSITIONALITY AND REACHABILITY WITH CONDITIONS ON PATH LENGTHS
• On the complexity of decision using destinies in \(H\)-bounded structures
• On countable chains having decidable monadic theory
• Peano arithmetic may not be interpretable in the monadic theory of linear orders
• Limited set quantifiers over countable linear orderings
• An algebraic approach to MSO-definability on countable linear orderings
• On the bounded monadic theory of well-ordered structures
• Bisimulation Invariant Monadic-Second Order Logic in the Finite
• Composition over the natural number ordering with an extra binary relation
• Model checking parameterised multi-token systems via the composition method
• Elementary equivalence of topological spaces

This page was built for publication: The monadic theory of order

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