Pattern Languages were introduced by Dana Angluin in the context of machine learning.
For example, using the constants Σ = { 0, 1 } and the variables X = { x, y, z, ... }, the pattern 0x10xx1 ∈P1 and xxy ∈P2 has length 7 and 3, respectively.
The language of the pattern x0 and x1 is the set of all bit strings which denote an even and odd binary number, respectively.
However, any two patterns p and q, of arbitrary lengths, generate the same language if and only if they are equal up to consistent variable renaming.
[5] Each pattern p is a common generalization of all strings in its generated language L(p), modulo associativity of (⋅).
NP-hardness of pattern language membership, by
reduction
from the
NP-complete
1-in-3-SAT problem
: Given a
CNF
of
m
clauses with
n
variables, a pattern of length 3
n
+4
m
+1 with 2
n
variables and a string of length
4
n+5
m
+1 can be constructed as shown (
m
=3 and
n
=4 in the example). Upper-case variables in the pattern correspond to negated variables in the CNF. The string matches the pattern if and only if an assignment exists such that in each clause exactly one literal is 1 (meaning "
true
" in the CNF). In the left part, e.g. "0
wW
0" is matched by "01110" just if one of
w
,
W
is matched by "1" (corresponding to "
false
") and the other by "11" (corresponding to "
true
"), i.e. if
w
corresponds to the negation of
W
. In the right part, e.g. "0
xYZ
0" is matched by "011110" just if exactly one of
x
,
Y
,
Z
is matched by "11" and the others by "1", i.e. if exactly one literal corresponds to "
true
".
