Graph subshifts

DOI10.1007/978-3-031-36978-0_21MaRDI QIDQ6149050zbMATH OpenFDO

Authors

Publication date 12 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Logic in computer science (03B70) Theory of computing (68Qxx)

Abstract: We propose a definition of graph subshifts of finite type that can be seen as extending both the notions of subshifts of finite type from classical symbolic dynamics and finitely presented groups from combinatorial group theory. These are sets of graphs that are defined by forbidding finitely many local patterns. In this paper, we focus on the question whether such local conditions can enforce a specific support graph, and thus relate the model to classical symbolic dynamics. We prove that the subshifts that contain only infinite graphs are either aperiodic, or feature no residual finiteness of their period group, yielding non-trivial examples as well as two natural undecidability theorems.

Recommendations

• On subshift presentations
• Shannon graphs, subshifts and lambda-graph systems.
• Aperiodic subshifts of finite type on groups which are not finitely generated
• A characterization of subshifts with computable language
• Strongly aperiodic subshifts on surface groups

Cites work

• scientific article; zbMATH DE number 3898244 (Why is no real title available?)
• A note on tilings and translation surfaces
• An Introduction to Symbolic Dynamics and Coding
• Combinatorial group theory.
• Endomorphisms and automorphisms of the shift dynamical system
• Induction and restriction of cellular automata
• Logical aspects of Cayley-graphs: the group case
• Remarks on Berger's paper on the domino problem
• Reversibility vs Local Creation/Destruction
• Some two-generator one-relator non-Hopfian groups
• Symbolic dynamics on free groups
• The Nilpotency Problem of One-Dimensional Cellular Automata
• The undecidability of the domino problem
• The undecidability of the domino problem
• Weak colored local rules for planar tilings
• When periodicities enforce aperiodicity

Cited in

(2)

• Cutting corners
• Decision problems on geometric tilings. Wang potatoes and finite local complexity

This page was built for publication: Graph subshifts

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