Słowa Fibonacciego – ciąg słów stosowany w informatyce teoretycznej między innymi do analizy złożoności algorytmów tekstowych.
Definicja słów Fibonacciego Słowa Fibonacciego są słowami nad alfabetem zdefiniowany rekurencyjnie jako:
Gdzie symbol oznacza konkatenację.
Początkowe słowa Fibonacciego
Własności słów Fibonacciego gdzie jest -tą liczbą Fibonacciego.
Niech oznacza słowo z ostatnimi dwoma literami zamienionymi kolejnością. Zachodzi:
Zobacz też słowo Thuego-Morse’a
Uwagi Nie ma jednej konwencji dotyczącej oznaczania początkowych słów Fibonacciego. W niektórych źródłach przyjmuje się w innych z kolei
Alfabet nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu lub innego dwuznakowego.
Bibliografia
Linki zewnętrzne Fibonacci word , Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].
Kategoria:Algorytmika