Subshifts as models for MSO logic

DOI10.1016/j.ic.2013.01.003zbMath1435.03064arXiv0912.1272OpenAlexW2023267442MaRDI QIDQ384929

Guillaume Theyssier, Emmanuel Jeandel

Publication date: 29 November 2013

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.1272

zbMATH Keywords

symbolic dynamicstilingsmodel theory

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Nonclassical models (Boolean-valued, sheaf, etc.) (03C90) Higher-order logic (03B16)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic and model-theoretic properties of tilings
• Elements of finite model theory.
• Logical aspects of Cayley-graphs: the group case
• The structure of the models of decidable monadic theories of graphs
• Languages and scanners
• Subshifts of finite type and sofic systems
• An existential locality theorem
• Monadic second-order logic over rectangular pictures and recognizability by tiling systems
• Undecidability and nonperiodicity for tilings of the plane
• Rice’s Theorem for μ-Limit Sets of Cellular Automata
• Intrinsic Universality in Self-Assembly
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• On Factor Universality in Symbolic Spaces
• Framed Versus Unframed Two-Dimensional Languages
• Subshifts, Languages and Logic
• On some conjectures connected with complete sentences
• An Introduction to Symbolic Dynamics and Coding
• On Local Symmetries and Universality in Cellular Automata
• The undecidability of the domino problem

This page was built for publication: Subshifts as models for MSO logic