Modest theory of short chains. I

DOI10.2307/2273287zbMath0464.03013OpenAlexW1966875984MaRDI QIDQ3914954

Yuri Gurevich

Publication date: 1979

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

modest chainsdecidability and axiomatizability in monadic theories of rationals and realsFraisse-Ehrenfeucht method for monadic theoriesmonadic theory of order

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Decidability of theories and sets of sentences (03B25) Continuum hypothesis and Martin's axiom (03E50) Second- and higher-order model theory (03C85) Quantifier elimination, model completeness, and related topics (03C10)

Related Items (29)

Towards a language theory for infinite N-free pomsets. ⋮ On countable chains having decidable monadic theory ⋮ On the complexity of decision using destinies in \(H\)-bounded structures ⋮ Simple monadic theories and partition width ⋮ Factorization forests for infinite words and applications to countable scattered linear orderings ⋮ On spectra of sentences of monadic second order logic with counting ⋮ On the strength of the interpretation method ⋮ Algorithmic uses of the Feferman-Vaught theorem ⋮ Logics of Finite Hankel Rank ⋮ Composition Over the Natural Number Ordering with an Extra Binary Relation ⋮ Courcelle's theorem -- a game-theoretic approach ⋮ Counting on CTL\(^*\): On the expressive power of monadic path logic ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ On integrability in elementary functions of certain classes of complex nonautonomous equations ⋮ A Feferman-Vaught Decomposition Theorem for Weighted MSO Logic. ⋮ Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory ⋮ Expressing cardinality quantifiers in monadic second-order logic over chains ⋮ Rabin's uniformization problem ⋮ Effective optimization with weighted automata on decomposable trees ⋮ On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic ⋮ On Monadic Theories of Monadic Predicates ⋮ Linear Recurrence Relations for Graph Polynomials ⋮ Decidable Expansions of Labelled Linear Orderings ⋮ A.D. Taimanov and model theory in Kazakhstan ⋮ Calculation of aerosol particle trajectories in the velocity hodograph plane ⋮ Modest theory of short chains. II ⋮ A logic-based approach to incremental reasoning on multi-agent systems ⋮ Definability and undefinability with real order at the background ⋮ The structure of the models of decidable monadic theories of graphs

Cites Work

• The monadic theory of order
• Monadic theory of order and topology, I
• Modest theory of short chains. II

This page was built for publication: Modest theory of short chains. I