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ößeFormat 
10.4171-ggd-689.pdf478,98 kBAdobe PDFÖffnen/Anzeigen


Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons