Informally the problem can be described as follows. Given a dictionary that contains pairs of phrases, i.e., a list of words, that mean the same, decide if there is a sentence that means the same in both languages.
The input of the problem consists of two finite lists:
of words over some alphabet Σ with at least two symbols. A solution to this problem is a sequence of indexes i_{1}, ..., i_{k}, 1 <= i_{j} <= n, such that
Consider the following two lists:
u_{1} u_{2} u_{3} u_{4} v_{1} v_{2} v_{3} v_{4} "aba" "bbb" "aab" "bb" "a" "aaa" "abab" "babba"A solution to this problem would be the sequence 1, 4, 3, 1 because