Algorithms for detecting morphic images of a word. (English) Zbl 0835.68091

Summary: Let \(\Delta\) and \(\Sigma\) be two disjoint finite alphabets. Given a “pattern” \(R\in (\Delta\cup \Sigma)^*\) and a “text” \(w\in \Sigma^*\), we consider the problem that consists in deciding whether there exists a morphism \(\varphi: (\Delta\cup \Sigma)^*\to \Sigma^*\), with \(\varphi (a)=a\) for every constant \(a\in \Sigma\), and such that \(\varphi (R)\) is a factor of \(w\). In the general case, this is an NP- complete problem. We study the two following restrictions:
\(R\) is an arbitrary one-variable pattern with constants (elements in \(\Sigma\)), \(R\) is a two-variable pattern without constant.
In the first case, we show that the problem may be solved by an \(O(|w|^2 \ln|w|)\)-time algorithm. In the second case, we present a \(O(|w|^2 \ln^2 |w|)\)-time algorithm for solving the question.


68R15 Combinatorics on words
68W10 Parallel algorithms in computer science
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI