Detecting morphic images of a word: On the rank of a pattern (Q1899100)

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 \textit{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. \textit{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.