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
The decision problem then is to decide whether such a solution exists or not.
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
If the two lists would have consisted of, for example, only u_{1}, u_{2}, u_{3} and v_{1}, v_{2}, v_{3} then there would have been no solution.
Search Encyclopedia

Featured Article
