Detecting morphic images of a word: On the rank of a pattern. (English) Zbl 0843.68106

Let \(\Delta\) and \(\Sigma\) be two disjointed alphabets. The elements of \(\Delta\) are the variables, and those of \(\Sigma\) are the constants. This paper takes place in a series of studies concerning the general problem which consists in detecting all the morphic images of a given word \(R \in (\Delta \cup \Sigma)^*\) (the “pattern”), in an arbitrary word \(w \in \Sigma^*\) (the “text”).
As a direct consequence of a work of D. Angluin, J. Comput. Syst. Sci. 21, 46-62 (1980; Zbl 0454.68108), this is an NP-complete problem. In fact, the naive algorithm runs in time \(O (|w |^{|\Delta |+ 2})\). Moreover, only the special case of “periodicities” (i.e. one variable patterns without constant of type \(X^n\), or two variables patterns of type \((XY)^n X)\) were studied in the literature [see e.g. M. G. Main, Discrete Applied Math. 25, No. 1/2, 145-153 (1989; Zbl 0683.68033)]. In the following papers, we have studied other special classes of restrictions: the author, Bull. Belg. Math. Soc. 1, 253-283 (1994; Zbl 0803.68097), Proceedings of MFCS’93, Lecture Notes Comput. Sci. 711, 588-597) and an extended version of the preceding paper, to appear in Inform. and Computation. Particularly, in the third paper, we proposed an \(O (|w |^2 \ln |w |)\) \((O (|w |^2 \ln^2 |w |))\)-time algorithm for solving the problem in the special case of an arbitrary one-variable pattern (two-variable pattern without constants) like \(X ab X^2 bac X a X\) \((XY X^2 Y^3 XY)\). Moreover (excepted in trivial cases of pattern) our algorithms allowed to detect all the possibles configurations \((u,h (R),v)\), with \(w = uh (r)v\).
However, the question of improving the general algorithm remains open. In our new paper, we present an improvement, by introducing the mathematical concept of “rank of a pattern”. Briefly, this notion consists in an integer, namely \(r(R)\), which allows to measure the (minimal) reconstruction of \(R\) in term of periodicity (the periodicities being interpreted in term of binary relations).
After having established some algebraical properties of the rang, we show that it can be computed in time \(O (|R |^3)\). After that, given an arbitrary word \(w \in \Sigma^*\), we show that detecting all the configurations \((u,h (R), v)\) may be done in time \(O (|w |^{|R |+ 1} r(R))\). In fact, the integer \(r(R)\) is up-bounded by \(|R |\) and, in most of the cases, \(r(R)\) is very small compared to this integer. We conclude the paper by mentioning some new improvement, and questions concerning the problem of detecting morphic images in a word.
Reviewer: Jean Neraud


68T10 Pattern recognition, speech recognition
68Q45 Formal languages and automata
Full Text: DOI


[1] [An 80] Angluin, D.: Finding Patterns common to a set of strings. J. Comput. Syst. Sci.21, 46–62 (1980) · Zbl 0454.68108
[2] [AP 83] Apostolico, A., Preparata, F.P.: Optimal off-line detection of repetitions in a string. Theoret. Comput. Sci.22, 297–315 (1983) · Zbl 0497.68052
[3] [B 92] Baker, K.: Open problems on avoidable and unavoidable patterns. Manuscript, Université de Rouen, France
[4] [C 81] Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Proc. Lett.12, 244–250 (1981) · Zbl 0467.68075
[5] [CR 91] Crochemore, M.: Rytter, W.: Periodic prefixes of strings. In: Acts of Sequences ’91, 1991
[6] [GS 83] Galil, Z., Seiferas, J.: Saving space in fast string-matching. SIAM J. Comput. 417–438 (1980) · Zbl 0446.68041
[7] [KMP 77] Knuth, D., Morris, J., Pratt, V.: Fast pattern matching in string. SIAM J. Comput.6 (2), 323–350 (1977) · Zbl 0372.68005
[8] [Lo 83] Lothaire, M.: Combinatorics on words. Encyclopedia of Mathematics and Appl. Reading: Addison-Wesley 1983
[9] [ML 85] Main, G., Lorentz, J.: Linear time recognition of squarefree strings In: Apostolico, A., Galil, Z. (eds.) Combinatoric Algorithms on Words: NATO ASI. Berlin: Springer 1985 · Zbl 0572.68068
[10] [N 93] Néraud, J.: New algorithms for detecting morphic images of a word. In: Proc. MFCS ’93, Vol. 711, pp. 588–597, 1993; Néraud, J.: Algorithms for detecting morphic images of a word. Inf. Computat.
[11] [N 94] Néraud, J.: Equations in words: an algorithmic contribution. Bull. Belg. Math. Soc.1, 253–283 (1994) · Zbl 0803.68097
[12] [R 85] Rabin, O.: Discovering repetitions in strings. In: Apostolico, A., Galil, Z. (eds.) Combinatoric algorithms on Words; NATO ASI. Berlin, Springer 1985
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.