Given a finite set Σ of constant symbols and a countable set X of variable symbols disjoint from Σ, a pattern is a finite non-emptystring of symbols from Σ∪X.
The length of a pattern p, denoted by |p|, is just the number of its symbols.
The set of all patterns containing exactly n distinct variables (each of which may occur several times) is denoted by Pn, the set of all patterns at all by P*.
A substitution is a mapping f: P* → P* such that[note 1]
f is non-erasing, formally: ∀p∈P*. f(p) ≠ ε, where ε denotes the empty string; and
f respects constants, formally: ∀s∈Σ. f(s) = s.
If p = f(q) for some patterns p, q ∈ P* and some substitution f, then p is said to be less general thanq, written p≤q;
in that case, necessarily |p| ≥ |q| holds.
For a pattern p, its language is defined as the set of all less general patterns that are built from constants only, formally: L(p) = { s ∈ Σ+ : s ≤ p }, where Σ+ denotes the set of all finite non-empty strings of symbols from Σ.
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.
An instance of the former pattern is 00z100z0z1 and 01z101z1z1, it is obtained by the substitution that maps x to 0z and to 1z, respectively, and each other symbol to itself. Both 00z100z0z1 and 01z101z1z1 are also instances of xxy. In fact, L(0x10xx1) is a subset of L(xxy). The language of the pattern x0 and x1 is the set of all bit strings which denote an even and odd binary number, respectively. The language of xx is the set of all strings obtainable by concatenating a bit string with itself, e.g. 00, 11, 0101, 1010, 11101110 ∈ L(xx).
Properties
NP-hardness of pattern language membership, by reduction from the NP-complete1-in-3-SAT problem: Given a CNF of m clauses with n variables, a pattern of length 3n+4m+1 with 2n variables and a string of length 4n+5m+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. "0wW0" 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. "0xYZ0" 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".
The problem of deciding whether s ∈ L(p) for an arbitrary string s ∈ Σ+ and pattern p is NP-complete (see picture),
and so is hence the problem of deciding p ≤ q for arbitrary patterns p, q.[2]
The class of pattern languages is not closed under ...
union: e.g. for Σ = {0,1} as above, L(01)∪L(10) is not a pattern language;
complement: Σ+ \ L(0) is not a pattern language;
intersection: L(x0y)∩L(x1y) is not a pattern language;
If p, q ∈ P1 are patterns containing exactly one variable, then p ≤ q if and only if L(p) ⊆ L(q);
the same equivalence holds for patterns of equal length.[4]
For patterns of different length, the above example p = 0x10xx1 and q = xxy shows that L(p) ⊆ L(q) may hold without implying p ≤ q.
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 (⋅).
Location in the Chomsky hierarchy
In a refined Chomsky hierarchy, the class of pattern languages is a proper superclass and subclass of the singleton[note 2] and the indexed languages, respectively, but incomparable to the language classes in between; due to the latter, the pattern language class is not explicitly shown in the table below.
the pattern language L(xx) is not context-free (hence neither regular nor finite) due to the pumping lemma;
the finite (hence also regular and context-free) language { 01, 10 } is not a pattern language.
Each singleton language is trivially a pattern language, generated by a pattern without variables.
Each pattern language can be produced by an indexed grammar:
For example, using Σ = { a, b, c } and X = { x, y },
the pattern axbycxayb is generated by a grammar with nonterminal symbols N = { Sx, Sy, S } ∪ X, terminal symbols T = Σ, index symbols F = { ax, bx, cx, ay, by, cy }, start symbol Sx, and the following production rules:
Sx[σ]
→ Sx[ax σ]
| Sx[bx σ]
| Sx[cx σ]
| Sy[σ]
Sy[σ]
→ Sy[ay σ]
| Sy[by σ]
| Sy[cy σ]
| S[σ]
S[σ]
→ ax[σ] by[σ] cx[σ] ay[σ] b
x[ax σ]
→ a
x[σ]
y[ax σ]
→
y[σ]
x[bx σ]
→ b
x[σ]
y[bx σ]
→
y[σ]
x[cx σ]
→ c
x[σ]
y[cx σ]
→
y[σ]
x[ay σ]
→
x[σ]
y[ay σ]
→ a
y[σ]
x[by σ]
→
x[σ]
y[by σ]
→ b
y[σ]
x[cy σ]
→
x[σ]
y[cy σ]
→ c
y[σ]
x[]
→ ε
y[]
→ ε
An example derivation is:
Sx[]
⇒ Sx[bx]
⇒ Sx[axbx]
⇒ Sy[axbx]
⇒ Sy[cyaxbx]
⇒ S[cyaxbx]
⇒ ax[cyaxbx] by[cyaxbx] cx[cyaxbx] ay[cyaxbx] b
⇒ ax[axbx] by[cyaxbx] cx[cyaxbx] ay[cyaxbx] b
⇒ aax[bx] by[cyaxbx] cx[cyaxbx] ay[cyaxbx] b
⇒ aabx[] by[cyaxbx] cx[cyaxbx] ay[cyaxbx] b
⇒ aabby[cyaxbx] cx[cyaxbx] ay[cyaxbx] b
⇒ ... ⇒ aabbcy[] cx[cyaxbx] ay[cyaxbx] b
⇒ aabbccx[cyaxbx] ay[cyaxbx] b
⇒ ... ⇒ aabbccabx[] ay[cyaxbx] b
⇒ aabbccabay[cyaxbx] b
⇒ ... ⇒ aabbccabacy[] b
⇒ aabbccabacb
In a similar way, an index grammar can be constructed from any pattern.
Learning patterns
Given a sample set S of strings, a pattern p is called descriptive of S if S ⊆ L(p), but not S ⊆ L(q) ⊂ L(p) for any other pattern q.
Given any sample set S, a descriptive pattern for S can be computed by
enumerating all patterns (up to variable renaming) not longer than the shortest string in S,
selecting from them the patterns that generate a superset of S,
selecting from them the patterns of maximal length, and
selecting from them a pattern that is minimal with respect to ≤.[6]
Based on this algorithm, the class of pattern languages can be identified in the limit from positive examples.[7]
Notes
^Angluin's notion of substitution differs from the usual notion of string substitution.
Each category of languages, except those marked by a *, is a proper subset of the category directly above it.Any language in each category is generated by a grammar and by an automaton in the category in the same line.
