Fibonacci arrays and their two-dimensional repetitions

被引：18

作者：

Apostolico, A

Brimkov, VE

机构：

[1] Univ Padua, Dipartimento Elettron & Informat, I-35131 Padua, Italy

[2] Purdue Univ, Dept Comp Sci, W Lafayette, IN 47904 USA

[3] Bulgarian Acad Sci, Inst Math & Informat, BU-1113 Sofia, Bulgaria

来源：

THEORETICAL COMPUTER SCIENCE | 2000年 / 237卷 / 1-2期

基金：

英国工程与自然科学研究理事会; 美国国家科学基金会;

关键词：

pattern matching; two-dimensional repetition; Fibonacci array;

D O I：

10.1016/S0304-3975(98)00182-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 x n Fibonacci array attains the general upper bound of O(m(2)n log n). (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：263 / 273

页数：11

共 14 条

[1]

AMIR A, 1992, PROCEEDINGS OF THE THIRD ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P440

[2] OPTIMAL OFF-LINE DETECTION OF REPETITIONS IN A STRING [J].

APOSTOLICO, A ;

PREPARATA, FP .

THEORETICAL COMPUTER SCIENCE, 1983, 22 (03) :297-315

[3] An optimal O(log log N)-time parallel algorithm for detecting all squares in a string [J].

Apostolico, A ;

Breslauer, D .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1318-1331

[4]

Cole R., 1993, Proceedings. 34th Annual Symposium on Foundations of Computer Science (Cat. No.93CH3368-8), P248, DOI 10.1109/SFCS.1993.366862

[5] TRANSDUCERS AND REPETITIONS [J].

CROCHEMORE, M .

THEORETICAL COMPUTER SCIENCE, 1986, 45 (01) :63-86

[6] AN OPTIMAL ALGORITHM FOR COMPUTING THE REPETITIONS IN A WORD [J].

CROCHEMORE, M .

INFORMATION PROCESSING LETTERS, 1981, 12 (05) :244-250

[7]

CROCHEMORE M, 1993, P SEQ 91 WORKSH SEQ, V2, P153

[8]

Galil Z., 1992, Proceedings 33rd Annual Symposium on Foundations of Computer Science (Cat. No.92CH3188-0), P247, DOI 10.1109/SFCS.1992.267767

[9]

GALIL Z, 1992, ALPHABET INDEPENDENT

[10]

Iliopoulos C. S., 1996, Parallel Processing Letters, V6, P299, DOI 10.1142/S0129626496000297

← 1 2 →