Notions related to repetitive substructures in two-dimensional arrays are introduced and studied in an attempt to parallel some of the analogous developments already known for strings. In particular, sequences of “Fibonacci arrays” are defined, capable of exhibiting extremal properties in terms of certain repetitive subpatterns called “tandems”. Two types of tandems are considered. For one type, it is shown that the number of occurrences in an m×n Fibonacci array attains the general upper bound of O(m^2nlogn).
Fibonacci arrays and their two-dimensional repetitions
APOSTOLICO, ALBERTO;
2000
Abstract
Notions related to repetitive substructures in two-dimensional arrays are introduced and studied in an attempt to parallel some of the analogous developments already known for strings. In particular, sequences of “Fibonacci arrays” are defined, capable of exhibiting extremal properties in terms of certain repetitive subpatterns called “tandems”. Two types of tandems are considered. For one type, it is shown that the number of occurrences in an m×n Fibonacci array attains the general upper bound of O(m^2nlogn).File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
