Melkemi, Lamine; Tchuente, Maurice Un réseau linéaire pour la reconnaissance des mots sans carré. (A linear array for recognition of square free words). (French) Zbl 0645.68088 RAIRO, Inf. Théor. Appl. 22, No. 2, 147-161 (1988). We introduce a parallel special-purpose architecture for the linear time recognition of square free words. The array presented is linear and only one of the basic cells can communicate with the external world. The processing of a word of length \(n=2p\) is performed in time \(T=3n\) on an array of size p, where the cycle-time of the basic cell is taken as time unit. MSC: 68Q45 Formal languages and automata 68Q80 Cellular automata (computational aspects) Keywords:linear array; linear time recognition; square free words PDFBibTeX XMLCite \textit{L. Melkemi} and \textit{M. Tchuente}, RAIRO, Inform. Théor. Appl. 22, No. 2, 147--161 (1988; Zbl 0645.68088) Full Text: DOI EuDML References: [1] 1. A. APOSTOLICO et A. NEGRO, Systolic Algorithms for String Manipulations, I.E.E.E. TC, C33, 4, 1984, p. 361-364. Zbl0528.68067 · Zbl 0528.68067 [2] 2. A. APOSTOLICO et F. P. PREPARATA, Optimal Off-Line Détection of Repetitions in a String, Theor. Comp. Sci., vol. 22, 1983, p. 297-315. Zbl0497.68052 MR693062 · Zbl 0497.68052 [3] 3. M. CROCHEMORE, An Optimal Algorithm for Computing the Repetitions in a String, Information processing letters, vol. 12, 1981, p. 244-250. Zbl0467.68075 MR632873 · Zbl 0467.68075 [4] 4. M. CROCHEMORE, Recherche linéaire d’un carré dans un mot, C.R. Acad. Sci. Paris, t. 296, série I, 1983, p. 781-784. Zbl0522.68074 MR707557 · Zbl 0522.68074 [5] 5. H. T. KUNG, Why Systolic Architectures, Computer Magazine, vol. 15, n^\circ 1, janvier 1982, p. 37-46. [6] 6. M. MAIN et R. LORENTZ, Linear Time Récognition of Square-Free Strings, dans Proceedings of the Nato Advanced Research Workshop on Combinatorial Algorithms on Words, Maratea, Italy, 1984, p. 271-278. Zbl0572.68068 MR815345 · Zbl 0572.68068 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.