Pattern Language (formal Languages)

In theoretical computer science, a pattern language is a formal language that can be defined as the set of all particular instances of a string of constants and variables. Pattern Languages were introduced by Dana Angluin in the context of machine learning.

Definition

Given a finite set Σ of constant symbols and a countable set ''X'' of variable symbols disjoint from Σ, a pattern is a finite non-empty string 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 ''P''_''n'', the set of all patterns at all by ''P''_*.
A substitution is a mapping ''f'': ''P''_* → ''P''_* such thatAngluin's notion of substitution differs from the usual notion of string substitution.
* ''f'' is a homomorphism with respect to string concatenation (⋅), formally: ∀''p'',''q''∈''P''_*. ''f''(''p''⋅''q'') = ''f''(''p'')⋅''f''(''q'');
* ''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 than ''q'', 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'') = , where Σ⁺ denotes the set of all finite non-empty strings of symbols from Σ.

For example, using the constants Σ = and the variables ''X'' = , the pattern 0''x''10''xx''1 ∈''P''₁ and ''xxy'' ∈''P''₂ has length 7 and 3, respectively.
An instance of the former pattern is 00''z''100''z''0''z''1 and 01''z''101''z''1''z''1, it is obtained by the substitution that maps ''x'' to 0''z'' and to 1''z'', respectively, and each other symbol to itself. Both 00''z''100''z''0''z''1 and 01''z''101''z''1''z''1 are also instances of ''xxy''. In fact, ''L''(0''x''10''xx''1) is a subset of ''L''(''xxy''). The language of the pattern ''x''0 and ''x''1 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

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''.

The class of pattern languages is not closed under ...
* union: e.g. for Σ = as above, ''L''(01)∪''L''(10) is not a pattern language;
* complement: Σ⁺ \ ''L''(0) is not a pattern language;
* intersection: ''L''(''x''0''y'')∩''L''(''x''1''y'') is not a pattern language;
* Kleene plus: ''L''(0)⁺ is not a pattern language;
* homomorphism: ''f''(''L''(''x'')) = ''L''(0)⁺ is not a pattern language, assuming ''f''(0) = 0 = ''f''(1);
* inverse homomorphism: ''f''⁻¹(111) = is not a pattern language, assuming ''f''(0) = 1 and ''f''(1) = 11.
The class of pattern languages is closed under ...
* concatenation: ''L''(''p'')⋅''L''(''q'') = ''L''(''p''⋅''q'');
* reversal: ''L''(''p'')^rev = ''L''(''p''^rev).

If ''p'', ''q'' ∈ ''P''₁ 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.
For patterns of different length, the above example ''p'' = 0''x''10''xx''1 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.
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 singletoni.e. languages consisting of a single string; they correspond to straight-line grammars 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 class of pattern languages is incomparable with the class of finite languages, with the class of regular languages, and with the class of context-free languages:
* 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 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 Σ = and ''X'' = ,
the pattern ''a'' ''x'' ''b'' ''y'' ''c'' ''x'' ''a'' ''y'' ''b'' is generated by a grammar with nonterminal symbols ''N'' = ∪ ''X'', terminal symbols ''T'' = Σ, index symbols ''F'' = , start symbol ''S''_''x'', and the following production rules:

An example derivation is:

  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒  
  ⇒ ... ⇒  
  ⇒  
  ⇒ ... ⇒  
  ⇒  
  ⇒ ... ⇒  
  ⇒  

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 ≤.
Based on this algorithm, the class of pattern languages can be identified in the limit from positive examples.; here: Example 1, p.125

Notes

References

{{formal languages and grammars

Formal languages
Theoretical computer science
Machine learning