Elastic-degenerate string comparison

An elastic-degenerate (ED) string T is a sequence of n sets T[1],…,T[n] containing m strings in total whose cumulative length is N. We call n, m, and N the length, the cardinality and the size of T, respectively. The language of T is defined as L(T)={S₁⋯S_n:S_i∈T[i] for all i∈[1,n]}. Given two ED strings, how fast can we check whether the two languages they represent have a nonempty intersection? We call this problem the ED STRING INTERSECTION (EDSI) problem. For two ED strings T₁ and T₂ of lengths n₁ and n₂, cardinalities m₁ and m₂, and sizes N₁ and N₂, respectively, we show the following: • There is no O((N₁N₂)^1−ϵ)-time algorithm, for any ϵ>0, for EDSI even if T₁ and T₂ are over a binary alphabet, unless the Strong Exponential-Time Hypothesis is false. • There is no combinatorial O((N₁+N₂)^1.2−ϵf(n₁,n₂))-time algorithm, for any ϵ>0 and any function f, for EDSI even if T₁ and T₂ are over a binary alphabet, unless the Boolean Matrix Multiplication conjecture is false. • An O(N₁log⁡N₁log⁡n₁+N₂log⁡N₂log⁡n₂)-time algorithm for outputting a compact representation of the intersection language of two unary ED strings. When T₁ and T₂ are given in a compact representation, we show that the problem is NP-complete. • An O(N₁m₂+N₂m₁)-time algorithm for EDSI. • An O˜(N₁^ω−1n₂+N₂^ω−1n₁)-time algorithm for EDSI, where ω is the matrix multiplication exponent; the O˜ notation suppresses factors that are polylogarithmic in the input size.