Computing longest common extensions in partial words

The paper builds upon a conference paper by the first author et al. [Lect. Notes Comput. Sci. 9538, 52--64 (2016; Zbl 1393.68137)]. A partial word over a finite alphabet \(\Sigma\) is a word over the extended alphabet \(\Sigma\cup\{\diamond\}\), where the symbol \(\diamond\) is referred to as a hole. Two partial words \(a_1\dots a_n\) and \(b_1\dots b_n\) are said to be compatible if for each \(i=1,\dots,n\), either \(a_i=b_i\) or \(\diamond\in\{a_i,b_i\}\). The Longest Common Compatible Extension (LCCE) of a pair \((i,j)\) of positions in a partial word \(w\) is the longest factor of \(w\) starting at \(i\) that is compatible with a factor of \(w\) starting at \(j\). The average length of the longest common compatible extension in all partial words of length \(n\) over an alphabet of cardinality \(\sigma\) with exactly \(h\) holes is denoted \(\mathrm{\mathtt Avg\_LCCE}(n,\sigma,h)\). The authors first prove (via direct but rather lengthy calculations) that for any fixed \(\sigma>1\) and constant \(h\geq1\), \(\lim_{n\to\infty}\mathrm{\mathtt Avg\_LCCE}(n,\sigma,h)=\frac{1}{\sigma-1}\) (Theorem 3.11); this proof has already been outlined in [loc. cit.]. Then the authors consider a probabilistic model in which the holes in a partial word are identically and independently distributed, i.e., any given position is a hole with some probability \(p_1\). They prove that for large values of \(n\) and fixed \(\sigma\), the average length of the LCCE over all partial words of length \(n\) over an alphabet of cardinality \(\sigma\) approaches \(\frac1{\sigma-1}\) as \(p_1\) approaches 0 (Theorem 4.8). In particular, \(\lim_{n\to\infty}\mathrm{\mathtt Avg\_LCCE}(n,\sigma,h)=\frac{1}{\sigma-1}\) whenever \(h=o(n)\). The paper also presents some experimental results. Reviewer's remark: \textit{B. Bollobás} and \textit{S. Letzter} [Eur. J. Comb. 68, 242--248 (2018; Zbl 1375.05006)] have established a similar result: \(\lim_{n\to\infty}\mathrm{\mathtt Avg\_LCCE}(n,\sigma,h)=\frac1{\sigma-1}\) whenever \(h=o(n^{1/3})\).

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Computing longest common extensions in partial words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1647840)