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)

• 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
• A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic.
• First-order separation over countable ordinals
• Monadic monadic second order logic
• Finite state automata and monadic definability of singular cardinals
• The monadic theory of order
• Index problems for game automata
• Effective optimization with weighted automata on decomposable trees
• Model Transformations in Decidability Proofs for Monadic Theories
• The subtrace order and counting first-order logic
• Pro-aperiodic monoids via saturated models
• The compositional method and regular reachability
• On the strength of some topological lattices
• On spectra of sentences of monadic second order logic with counting
• The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic
• Simple monadic theories and partition width
• Interpreting the weak monadic second order theory of the ordered rationals
• Decidability of Difference Logic over the Reals with Uninterpreted Unary Predicates
• On monadic theories of monadic predicates
• A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
• First-order theories of bounded trees
• Regular languages of words over countable linear orderings
• Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words
• On expressive power of regular expressions over infinite orders
• The monadic theory of \((\omega{}_ 2,<)\) may be complicated
• DOWNWARD UNARY COLORINGS
• Bisimulation invariant monadic-second order logic in the finite
• On labeled birooted tree languages: algebras, automata and logic
• Expressing cardinality quantifiers in monadic second-order logic over chains
• Non-emptiness test for automata over words indexed by the reals and rationals
• Logics of finite Hankel rank
• Axiomatizability of propositionally quantified modal logics on relational frames
• Asymptotic Monadic Second-Order Logic
• 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

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)