Substitutionssystemen

Substitutionssystemen zijn wiskundige constructies waarbij een alfabet wordt voorzien van vervangingsregels. Elke letter a uit het alfabet wordt vervangen door een woord w_a dat bestaat uit letters van hetzelfde alfabet. Door deze regels herhaaldelijk toe te passen op een beginwoord ontstaat een woord dat oneindig kan groeien of een complex patroon kan vormen. De structuur van het resultaat wordt bepaald door de vervangingsregels en de samenstelling van het alfabet.

Naast woordvorming bestaan substituties ook in hogere dimensies als tegelvervanging (tegelsubstituties), waarbij tegels worden vervangen door een verzameling tegels volgens een regel. Dit kan leiden tot aperiodische patronen, die voorkomen in bepaalde quasi-crystalachtige systemen en tilings.

Een centrale eigenschap is de substitutiematrix M, waarin M_{ij} het aantal keer letter i telt in de vervanging van letter j. Bij primitieve substituties heeft M een unieke Perron-Frobenius-eigenwaarde die de groeisnelheid van het woord bepaalt en zorgt voor voorspelbare statistische eigenschappen van de resulterende woord- of taalsysteem.

Een bekend voorbeeld is de Fibonacci-substitutie: a -> ab, b -> a. Startend met a levert dit de oneindige Fibonacci-woord op. Andere substituties worden bestudeerd in de combinatoriek op woorden en in de studie van symbolische dynamiek.

Toepassingen liggen in formele talen, symbolische dynamiek en in de constructie van quasi-crystalachtige tilings en computergegenereerde patronen. Substitutionssystemen bieden een framework voor het analyseren van structuur, repetitie en groeiprocessen in complexe linguïstische en geometrische systemen.