The monadic theory of order

DOI10.2307/1971037zbMath0345.02034OpenAlexW2062792526WikidataQ105487999 ScholiaQ105487999MaRDI QIDQ1233019

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

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

Related Items

Index Problems for Game Automata, The Subtrace Order and Counting First-Order Logic, On the Ehrenfeucht-Fraïssé game in theoretical computer science, DOWNWARD UNARY COLORINGS, THE COLORING OF THE TREE OF COLORINGS, Unnamed Item, On spectra of sentences of monadic second order logic with counting, Interpreting the weak monadic second order theory of the ordered rationals, A note on edge colorings and trees, Algebraic characterizations and block product decompositions for first order logic and its infinitary quantifier extensions over countable words, First-order separation over countable ordinals, Bisimulation Invariant Monadic-Second Order Logic in the Finite, A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic., Effective optimization with weighted automata on decomposable trees, On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic, On Expressive Power of Regular Expressions over Infinite Orders, Unnamed Item, Compositional Failure Detection in Structured Transition Systems, Linear Recurrence Relations for Graph Polynomials, Selection and Uniformization Problems in the Monadic Theory of Ordinals: A Survey, Unnamed Item, Decidable Expansions of Labelled Linear Orderings, Unnamed Item, Unnamed Item, The Compositional Method and Regular Reachability, A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS, LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE, Trees, grids, and MSO decidability: from graphs to matroids, Towards a language theory for infinite N-free pomsets., On countable chains having decidable monadic theory, The decision problem for branching time logic, On the complexity of decision using destinies in \(H\)-bounded structures, Simple monadic theories and partition width, Limited Set quantifiers over Countable Linear Orderings, On decidability of monadic logic of order over the naturals extended by monadic predicates, Time-Bounded Verification, The expressive power of Malitz quantifiers for linear orderings, Automata on linear orderings, Asymptotic Monadic Second-Order Logic, On decidability properties of local sentences, Notes on monadic logic. A: Monadic theory of the real line, On the strength of the interpretation method, Algorithmic uses of the Feferman-Vaught theorem, Propositional quantification in the topological semantics for \(\mathbf S4\), Toward classifying unstable theories, On translations of temporal logic of actions into monadic second-order logic, The expressive power of second-order propositional modal logic, Recursion Schemes and the WMSO+U Logic, MSOL partitioning problems on graphs of bounded treewidth and clique-width, Bisimulation invariant monadic-second order logic in the finite, Monadic Theory of a Linear Order Versus the Theory of its Subsets with the Lifted Min/Max Operations, Logics of Finite Hankel Rank, Composition Over the Natural Number Ordering with an Extra Binary Relation, The Caucal hierarchy: interpretations in the (W)MSO+\(\mathsf{U}\) logic, Taxonomies of model-theoretically defined topological properties, Monadic theory of order and topology. II, Elementary equivalence of topological spaces, Finite state automata and monadic definability of singular cardinals, Counting on CTL\(^*\): On the expressive power of monadic path logic, Stationary Logic and Ordinals, Temporal logics over linear time domains are in PSPACE, Continuous time temporal logic with counting, Weakly maximal decidable structures, On frontiers of regular trees, A syntactic congruence for languages of birooted trees, Automata and logics over finitely varying functions, Selection over classes of ordinals expanded by monadic predicates, Notes on monadic logic. Part B: Complexity of linear orders in ZFC, A Hierarchy of Automaticω-Words having a Decidable MSO Theory, 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, Model Transformations in Decidability Proofs for Monadic Theories, On the strength of some topological lattices, Arity hierarchy for temporal logics, Peano arithmetic may not be interpretable in the monadic theory of linear orders, Counting finite models, The monadic theory of \((\omega{}_ 2,<)\) may be complicated, Expressing cardinality quantifiers in monadic second-order logic over chains, Regular Languages of Words over Countable Linear Orderings, Rabin's uniformization problem, The Church problem for expansions of \((\mathbb{N},<)\) by unary predicates, CONTINUOUS RAMSEY THEORY ON POLISH SPACES AND COVERING THE PLANE BY FUNCTIONS, Uniformization and skolem functions in the class of trees, On Monadic Theories of Monadic Predicates, Logical aspects of Cayley-graphs: the group case, Recognizability, hypergraph operations, and logical types, Interpreting second-order logic in the monadic theory of order, The complete finitely axiomatized theories of order are dense, Timer formulas and decidable metric temporal logic, Logic and rational languages of words indexed by linear orderings, Substance and first-order quantification over individual-concepts, Monadic theory of order and topology, I, Pro-aperiodic monoids via saturated models, Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings, Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates, AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS, The full binary tree cannot be interpreted in a chain, On the bounded monadic theory of well-ordered structures, Decidable metric logics, A weak generalization of MA to higher cardinals, Selection in the monadic theory of a countable ordinal, Unnamed Item, Model Checking Parameterised Multi-token Systems via the Composition Method, Cardinality Quantifiers in MLO over Trees, Decidable Extensions of Church’s Problem, COMPOSITIONALITY AND REACHABILITY WITH CONDITIONS ON PATH LENGTHS, Modest theory of short chains. I, Modest theory of short chains. II, The factorisation forest theorem, The spectrum problem for abelian \(\ell\)-groups and MV-algebras, The recognizability of sets of graphs is a robust property, Monadic second-order logic, graph coverings and unfoldings of transition systems, Reflecting stationary sets, Uniformization, choice functions and well orders in the class of trees, Convex decompositions in the plane and continuous pair colorings of the irrationals, Monadic logic and Löwenheim numbers, On infinite transition graphs having a decidable monadic theory, State-strategies for games in F_σδ ∩ G_δσ, Stationary logic of ordinals, On the Weihrauch degree of the additive Ramsey theorem over the rationals, The monadic theory and the next world, On labeled birooted tree languages: algebras, automata and logic, The monadic second-order logic of graphs. IV: Definability properties of equational graphs, The structure of the models of decidable monadic theories of graphs, Monadic second-order logic on tree-like structures, Shelah-Stupp's and Muchnik's iterations revisited, First-order theories of bounded trees