Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-44624
Titel: | Monadic second-order logic and the domino problem on self-similar graphs |
VerfasserIn: | Bartholdi, Laurent |
Sprache: | Englisch |
Titel: | Groups, geometry, and dynamics : GGD |
Bandnummer: | 16 |
Heft: | 4 |
Seiten: | 1423-1459 |
Verlag/Plattform: | EMS Publ. |
Erscheinungsjahr: | 2022 |
Freie Schlagwörter: | Wang tiles monadic second-order logic self-similar graphs |
DDC-Sachgruppe: | 510 Mathematik |
Dokumenttyp: | Journalartikel / Zeitschriftenartikel |
Abstract: | We consider the domino problem on Schreier graphs of self-similar groups, and more generally their monadic second-order logic. On the one hand, we prove that if the group is bounded, then the domino problem on the graph is decidable; furthermore, under an ultimate periodicity condition, all its monadic second-order logic is decidable. This covers, for example, the Sierpiński gasket graphs and the Schreier graphs of the Basilica group. On the other hand, we prove undecidability of the domino problem for a class of self-similar groups, answering a question by Barbieri and Sablik, and study some examples including one of linear growth. |
DOI der Erstveröffentlichung: | 10.4171/ggd/689 |
URL der Erstveröffentlichung: | https://ems.press/journals/ggd/articles/8188707 |
Link zu diesem Datensatz: | urn:nbn:de:bsz:291--ds-446247 hdl:20.500.11880/39780 http://dx.doi.org/10.22028/D291-44624 |
ISSN: | 1661-7215 1661-7207 |
Datum des Eintrags: | 12-Mär-2025 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Mathematik |
Professur: | MI - Prof. Dr. Laurent Bartholdi |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
10.4171-ggd-689.pdf | 478,98 kB | Adobe PDF | Öffnen/Anzeigen |
Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons