Graph subshifts
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918477559758848 |
|---|---|
| author | Arrighi, Pablo Durbec, Amélia Guillon, Pierre |
| author_facet | Arrighi, Pablo Durbec, Amélia Guillon, Pierre |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_07249 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Graph subshifts Arrighi, Pablo Durbec, Amélia Guillon, Pierre Discrete Mathematics Formal Languages and Automata Theory Group Theory 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. |
| title | Graph subshifts |
| topic | Discrete Mathematics Formal Languages and Automata Theory Group Theory |
| url | https://arxiv.org/abs/2302.07249 |