## Training in structural pattern recognition.(Russian)Zbl 0635.68098

The training problem on structural objects is investigated. An structural object is a complete oriented graph with labels on every node and arc. These labels are elements of some vector space of features. The case when the number of nodes n is fixed and the labels of arcs have only two values (0 or 1) is considered. Such structures may be defined by a matrix $$\tilde g=\| g_{ij}\|_{n\times n}$$, where $$g_{ij}\in \{0,1\}$$. The pattern is the set of objects generating a matrix grammar $$GR=(V_ N,V_ T,P,S)$$, $$V_ N=\{S,B_{11},...,B_{nn}\}$$, $$V_ T=\{0,1\}$$, S the initial symbol, P the set of inference rules, including $S\to \left( \begin{matrix} B_{11},...,B_{1n}\\ B_{n1},...,B_{nn}\end{matrix} \right)\quad and\quad B_{ij}\to g_{ij}.$ This grammar is defined by some matrix $$\tilde w=\| w_{ij}\|_{n\times n}$$, where $$w_{ij}=\{g_{ij}\in \{0,1\}:$$ $$B_{ij}\to g_{ij}\}.$$
The training problem on objects and on objects with inserted and/or deleted arcs is formulated as the problem of inference of matrix grammar. The conditions of inferrability of such grammars are given. The complexity of training procedures is discussed.
Reviewer: N.Huhro

### MSC:

 68T10 Pattern recognition, speech recognition 68Q45 Formal languages and automata