A note on the two-variable pattern-finding problem (Q1097711): Difference between revisions

Pattern languages are defined by \textit{D. Angluin} [J. Comput. Syst. Sci. 21, 46-62 (1980; Zbl 0454.68108)] as an abstract model of learning one- dimensional patterns. A pattern is defined to be a string of variables and constants, and its associated language is defined to be all constant strings obtained by substituting constant strings for variables in the pattern. The pattern-finding problem is to identify a mysterious pattern from some examples of strings in the pattern language. Angluin found a polynomial-time algorithm for finding patterns of one variable. It is not known whether the problem is polynomial-time solvable or is NP-complete for the two-variable case. This paper shows that if one tries to generalize Angluin's one-variable algorithm to the two-variable case, then one would encounter a problem of finding a common path in a graph of multiple labels, and this problem is shown to be NP-complete. This result supports the conjecture that the two-variable pattern-finding problem is indeed NP-complete.