We introduce a family of finite pictures (i.e. two-dimensional words) by means of a recursive definition based on a Fibonacci-like scheme and using combined row and column concatenation operations between pictures. The resulting picture sizes are pairs of Fibonacci numbers. The limit of these pictures when growing their sizes is an infinite picture, we call F∞,∞, which includes all such pictures as top-left prefixes. Moreover, F∞,∞ constitutes an interlacing of the infinite Fibonacci word, that can be read along every path originating from the top-left corner and proceeding right and down. We study some interesting properties of the factors of F∞,∞ such as balancing and some kind of repetitions.
Anselmo, M., Giammarresi, D., Madonia, M., Selmi, C. (2025). Fibonacci Pictures on a Binary Alphabet. In Descriptional Complexity of Formal Systems (pp.1-16). GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND : Springer [10.1007/978-3-031-97100-6_1].
Fibonacci Pictures on a Binary Alphabet
Giammarresi, Dora;
2025-01-01
Abstract
We introduce a family of finite pictures (i.e. two-dimensional words) by means of a recursive definition based on a Fibonacci-like scheme and using combined row and column concatenation operations between pictures. The resulting picture sizes are pairs of Fibonacci numbers. The limit of these pictures when growing their sizes is an infinite picture, we call F∞,∞, which includes all such pictures as top-left prefixes. Moreover, F∞,∞ constitutes an interlacing of the infinite Fibonacci word, that can be read along every path originating from the top-left corner and proceeding right and down. We study some interesting properties of the factors of F∞,∞ such as balancing and some kind of repetitions.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
