---
title: "A Method of Pattern Recognition Using Rewriting Rules"
authors:
  - "Akira Kurematsu"
  - "Manabu Takeda"
  - "Seiichi Inoue"
doi: ""
url: "https://ijcai.org/proceedings/1971/28"
pdf: "https://ijcai.org/proceedings/1971/0028.pdf"
venue: "Proceedings of the Second International Joint Conference on Artificial Intelligence"
year: 1971
pages: "287-296"
track: ""
keywords:
---

# A Method of Pattern Recognition Using Rewriting Rules

Akira Kurematsu, Manabu Takeda, Seiichi Inoue

*Proceedings of the Second International Joint Conference on Artificial Intelligence*, pages 287-296.

## Abstract

This paper presents a method of applying rewriting rules to the recognition of patterns, structure of which are sequentially connected and can be expressed as symbol strings. Rewriting rules, which play the part of a recognizer, are formulated in a hierarchical structure. Rule 1 normalizes the length of string and extracts properties, rule 2 transforms the deformed string in a context dependent way and rule 3 determines the category. A procedure for producing rules from given sample patterns based on the similarity between the s y mbols and a procedure for modifying the ru l es when input patterns are added are described .. Experimental results of the recognition of Japanese spoken digits to illustrate the method are exhibited.

## Full text

## Introduction

Many efforts have been made to recog­ n ize compli cated patterns such as connected speech , handwritte n characters and image figures by the use of a machine. When abili­ ties are compa:-ed, however, a machine is not up to a human being in recognizing patterns.

In most cases, patterns are recognized b y the following method. The predetermined characteristic values of a giv en input pattern are calculated, and with a combination of the r e sults, the output is given to one of the pre­ established categories. However, as pointed out by Evans( I), it is difficult to improve the degradation in the performance with such a simpl e method when patterns are complicated, be cause patterns are recognized at one level. Mo reover, it is necessary to obtain more in­ fo rmation about pattern structure in a form be tt e r suited for further processing . In order to overcome such difficulties, the approach taken is directed to a hierarchical description of the structure of patterns in terms of sub­ patterns, their properties and the relations among them. Using this method, most of the in i tially designed recognizing machines can be utilized simply by anal yzing the subpatterns d ee pl y as required when the pattern is com­ pli c ated. In addi tion, advanced pattern processing can be made easily by the use of a computer because an input pattern can be transformed to a symbol string and expressed in a form so that the machine can handle them.

As a simple form to use the syntax structure of patterns, sequential logic has been adopted to recognize spoken digits or hand­ written characters and fairly good results have been ayi\ined. (2) · (3) As indicated by Alter(4) and Fu 5 J, it is necessary to utilize contextual constraints and a kncwledge of language struc­ sure to raise the recognition rate of continuous speech. As for the picture recognition, the idea of analyzing the structure of patterns is described initially in Minsky's "articular" description, (6) and many efforts have been made to research grammars and procedures for analysis suited to describe pictures. (7) · (8) · (9) However these have not led to a general theory especially in the stage to formulate grammars, although a few particular cases have been treated in some detail. The attempt to construct the general formalism intended to use in linguistic pattern analysis were outlined by Grenander(lO) .

This paper describes procedures for formulating rewriting rules for the recogni­ tion of patterns whose structure is one dimen­ sional such as speech patterns, from symbol strings of sample patterns, based on the similarity between the symbols . A procedure for modifying the rules, when input patterns other than those used for the sample patterns are added, is also described.(ll ) , ( 12) The above method was actually examined for the recognition of Japanese spoken digits, and this paper introduces the results.

## Scheme of Pattern Recognition

The scheme of the pattern recognition which we deal with in this paper is shown in Fig. 1. An input pattern observed by obser­ vation measurements is segmented into sub­ patterns whose unit is properly determined. The subpattern is expressed by a vector in the measurement space. An input pattern can be expressed as a sequence of subpatterns. The subpattern is classified into one of predetermined classes of subpatterns, which are called fundamental constituents. By the use of sym­ bols named to each fundamental constituent, the sequence of subpatterns is expressed as a string of symbols.

A symbol string of the pattern can be regarded as being generated by a set of the re­ writing rules. That is, a set of symbol strings of patterns is regarded as a phrase structure language. In the language theory, it is shown that various classes of phrase structure languages are derived from a finite number of alphabet of symbols and rules, imposing re­ strictions on grammars, although they are not adequate for formulation of a full grammar for a naturallanguage(l3), In this paper, the dis­ cussions are limited to the recognition of patterns such as limited spoken words, which are observed physically in the measurement space, therefore it can be assumed that the language is non-self-embedding and it is a finite state language. The content of a phrase in this case is a unit of a phonological forms which is sustained by the constrictions of the movements of human organs in making voice. These constrictions are expressed as rules.

A symbol string of the pattern is parsed by matching a sequence of a partial string by the use of rewriting rules. As a result of the parsing, a decision is made as to which cate­ gory an input pattern belongs. For example, a speech pattern can be expressed as a sequence of frequency patterns observed at a certain interval. The frequency spectrum pattern is classified in accordance with the properties. The symbol may correspond to the name of phoneme.

In deriving the rewntmg rules from the collection of sample patterns, the similarity between the symbols is considered to deter­ mine a group of symbols with common proper­ ties. The similarity between two subpatterns, X1, X2 is a scalar which represents a degree of likeness calculated in their measurement space. We denote it by~( X1, X2).

The similarity between two symbols S 1 , s2 is defined by d(S 1, s2) = ~(Xsl· Xs2l· where Xs 1 and Xs 2 are vectors representing the classes (standard patterns) corresponding to S1 and s 2 respectively.

We call a symbol attached to the funda­ mental constituent of a pattern a primitive symbol.

An intermediate symbol is named to a string of primitive symbols which share common properties and are considered to be a unit.

A symbol to express the category is called a category symbol.

We denote by S, Q, and P, respectively, primitive symbols, intermediate symbols and category symbols.

The structure of the rewriting rules for the pattern recognition is formulated in a hierarchical structure. The hierarchical structure is effective in reducing the number of rules and in shortening the time required to refer to the rules. Depth of the hierarchy differs depending upon the complexity of the pattern. In this paper, we proceed with our discussion based on a model of three levels.

The application of the rules in the recognition of a symbol string is illustrated in Fig. 2. A primitive symbol string is trans­ formed to an intermediate symbol string by rules of the 1st kind from left to right; the intermediate symbol string is transformed to another intermediate symbol string by rules of the 2nd kind from left to right; and, finally, the category is determined by rules of the 3rd kind.

The rule of the lst kind (rule 1) deal s with the extraction of properties from a primi ­ tive symbol string and the normalization of the length of a partial string, which, for example, is required for the recognition of speech spoken at different speeds.

The rule of the 2nd kind (rule 2) trans­ forms a partial string of intermediate symbols to another partial string. It deals with the normalization of the deformed patterns caused by various ways of production or the removal of the noise or the elimination of influences from neighboring subpattern lt is expressed in a context dependent form

The rule of the 3rd kind (rule 3) deter­ mines the category from a string of inter­ mediate symbols.

The rewriting rules can be formed in two structures;

- (1) Structure in which rules for each category are separated,
- (2) Structure in which rules for cate­ gories are combined.

In the separated structure, preparation and modification of the rules are easier although the number of rules increases, since rules are independent in the individual categories. In the combined structure, the number of rules can be reduced because rules existed together in two or more categories can be merged.

## Procedure to Formulate Rewrit­ ing rules

The following procedure is described to formulate the rewriting rules by analyzing the structure of strings of given sample patterns.

An outline of the procedure for formulat­ ing the rules is described as follows: first the ordering relations among primitive symbols and intermediate symbols are examined, then a standard sequence for each category is derived, and then relations between partial strings are expressed in the form of rules.

Before describing the procedure, we will explain several terms used in it.

Stable .symbol: A primitive symbol is called a stable symbol if it succeeds consecutively in more than a certain length (Ks ) . It corresponds to a stable portion in the pattern which will hardl y be influenced with a noise.

Ke y symbol: A primitive symbol is called a k e y symbol if it occurs more than a certain t imes (Kk) in the same relative relations in the set of samples of the same category. It corre­ sponds to the characteristics which are ob­ served commonly in almost all patterns of the same categor y . The Ks and Kk are determined with regard to the nature of the pattern. An example is shown in Tab.le 1 for the case that K 5 =Z and Kk= 3. Underlined symbol means the stable symbol.

Descendan t: A primitive symbol is called a descendant of an intermediate symbol, say Qi, if it is transformed to Qi by rules of the lst kind. A set of descendants of Qi is denoted by D (Qi) = { Si 1 , Siz, . . . } . A descendant is called a main descendant if it is a key symbol or if it occurs most frequently among the de­ scendants of an intermediate symbol.

Standard sequence: A sequence of intermediate symbols corresponding to key symbols of a category is called a standard sequence of the category.

0 rde ring relation: An ordering relation among primi tive symbols is an order of their occur­ rences in the set of primitive symbol strings of the same category.

Procedures to derive the rules from given sample patterns are described for two structures of rules.

## Structure to separate the rules for each category

Step 1: Examine the or de ring relations among primitive symbols for each category.

- Step Z: Determine stable symbols and key symbols for each category. A procedure to decide key symbols from symbol strings of given sample patterns is described in the Appendix.
- ~: Determine intermediate symbols and descendants for each category so that each primitive symbol may become a de­ scendant of any intermediate symbol.

First an intermediate symbol is assign­ ed to each key symbol. Next a primitive symbol which has not been picked up as a key symbol is assigned to a descendant in the following way. When there is a primitive symbol which is immediately in front of, rear of or in equal relation of the main descendant and the similarity to the main descendant is more than a certain value (Kd) , such a symbol is put into the descendant of the intermediate symbol.

When one primitive symbol is a candi­ date of more than two descendants, such a symbol becomes a descendant of the inter­ mediate symbol, the main descendant of which has the largest similarity value to the symbol. Those primitive symbols which are not assign­ ed to any descendants are assigned to de­ scendants of new intermediate symbols.

In the example shown in Table 1, inter­ mediate symbols and descendants are deter­ mined as shown in Table Z, when d(Sl, 56}> Kd, d(Sl, S4}> Kd, d (S3, S7}> Kd, d(Sg, s6) > Kd, d(Sz, 5 1}< Kd, d (Sz , So)< Kd, d(S5, 51}< Kd, d(Ss, So)< Kd and d(Sz, 5 5 }> Kd. It is to be noted that a new intermediate symbol a 4 is assigned to Sz, because d(Sz. SI) < Kd and d (Sz, So}< Kd. Encircled symbols indicate main descendants.

~: Form rules of the 1st kind based on the relations of intermediate symbols and descendants. When the length of a partial string to be transformed to the same intermediate symbol is not limited, rules !or D(Qi) = { Si 1, Si2 } , !or instance, are ex­ pressed as follows;

<!-- formula-not-decoded -->

A set of these rules is denoted by oi~ 5 ii· 5 i2;.

Step 5: Transform a primitive symbol string to an intermediate symbol string by applying rules o! the 1st kind and derive a standard sequence. Form rules o! the 3rd kind to transform a standard sequence to a category symbol. Table 3 shows intermediate symbol strings and a standard sequence o! sample patterns shown in the Table 1.

~: Form rules of the 2nd kind by comparing a partial string of a standard sequence with a partial intermediate symbol string of a sample pattern. When there is a partial string which does not coincide with that of a standard sequence, it is expressed in the rule. The rules formed to recognize sample patterns in the Table 1 are shown in Table 4.

## Structure to combine rules !or all categories

In the structure to combine rules for all categories, intermediate symbols and de­ scendants are to be merged because the rules are to be applied deterministically.

After the procedure proceeds !rom step 1 to step 3, intermediate symbols and de­ scendants decided separately by the individual categories are combined and merged as follows.

~·: Form a table indicating all intermediate symbols and their descendants !or individual categories. Merge and simplify the assignment o! intermediate symbols and their descendants so that each primitive symbol becomes only one descendant. The procedure to merge the assignment is performed so that rules should be formed as simply as possible. But details are not presented in this paper.

Thereafter, the process goes to step 4 in the same way as in the case of the separated structure described above. After the comple­ tion of step 6, rules of the 2nd and 3rd kinds !or all categories are combined.

Modification and Simplification of Rule

## Modification of rule

Rules are to be modified in the following

cases:

- (i) The case that there is any sample pattern which is not recognized correctly by the rules after the completion of the step 6 in the preceding section.
- (ii) The case that, after all given sample patterns are ascertained to be recognized correctly, other patterns, the category names of which are known, are not recog­ nized correctly.

The rules should be modified so that patterns recognized correctly before the modification should be recognized once again correctly after the modification. The procedure for modifying the rules with the knowledge of the old rules, the similarity between the symbols and the ordering relations of the symbols in each cate­ gory, is examined. The rules are modified in the following circumstances. Five cases v..-here rules should be modified are enumerated;

- (a) The first case is that an input pattern is recognized as belonging to more than two categories; we call such a grammar am­ biguous. This case occurs when the rules are separated into each category. In this case there are at least two symbols which commonll· occur in at least two categories. Those symbols are included commonly with other symbols in a set of descendants of a particular intermediate symbol in at least one of those categories.

For example, assume that two symbols, Sk and Sm· are included commonly in two categories i and j, and the following rules exist,

<!-- formula-not-decoded -->

where Qik and Oim are intermediate symbols in category i and Qjk is in category j. In this case a symbol string. w = sksm. is transformed to OikOim in the category i and transformed to Qjk in the category j, which causes ambiguity. A grammar is revised so that it becomes un­ ambiguous by adding a new intermediate symbol to the category where descendants are included common! y. In the example above, a new inter­ mediate symbol, Ojm is added to the category j, and rules of the 1st kind are modified as Ojm--+ Sm;, Ojk--+ Sk;. Rules of the 2nd kind are added in response to the change of rules of the 1st kind.

- (b) In the second case, a pattern is rejected because primitive symbols are not transformed to intermediate symbols by rules of the 1st kind. Primitive sy·mbols not trans­ formed are those which did not occur in the sample patterns used to construct the rules. The modification of the rules is carried out for rules of the 1st kind. The best assignment of primitive symbols to descendants is determined by the use of the values of the similarity between those primitive symbols and descendants.
- (c) In the third case, an input pattern is rejected because the intermediate symbol string is not transformed by any rules of the 3rd kind. This occurs due to the lack of rules of the 2nd kind to transform a partial string of intermediate symbols of an input pattern to a standard sequence of the corresponding cate­ go r y . For this problem, there are two so­ lutions; rules of the 2nd kind are added or rules of the 1st kind are changed so that descendants of intermediate symbols are replaced. In the latter case, however, rules of the 2nd kind may also have to be modified in response to the change in rules of the 1st kind. In either way, an inc rease in the number of the rules caused by the modification is examined , and whichever has less number of rules is adopted.
- (d) In the fourth case, an input pattern i s misrecognized because a set of symbol strings to be recognized as belonging to some category is so large that e ven a symbol string which is to be recognized as belonging to another category is included. This trouble occurs because there are so many descendants of some intermediate s ymbols that some string is recog­ nized as in more than two categories. In this c ase, rules of the I st and 2nd kinds are modifi­ ed so that a set of symbol strings to be recog­ nized for each category may become adequate.
- (e.) In the fifth case, an input pattern is not recognized correctly bec ause rules of the 2nd kind which should be applied to the string of another category are applied. This trouble oc curs when rules of all categories are combined, and the length of the context of rules of the 2nd kind is insufficient. In this case , the problem can be solved by inc rea sing the length of the context as required. An example is introduced as follows :

It is assumed that there is a set of rules expressed as follows in the rules of the 2nd kind:

- (a) QiQkQj -?OiQkQj (b) QkQJQm --+QkQjQm

Now, when the rules {a) and {b) are to be applied in this order for an intermediate symbol string of an input pattern expressed as W = QiQkQjQm, theW becomes QiQkQ ·Qm by the application of the rule (a). Howeve 1 r , when the recognition cannot be made correctly unless the W becomes QiQkQJQm using the rule (b), the length of the rule {b) must be increased to QiQkQJQm\_\_\_, QiQkQjOm·

## Simplification of rule

It is necessary to simplify the rules so that the number of rules is reduced by remain­ ing rules which are essential to the recognition and deleting those which do not contribute to the recognition. There are two ways to simplify the rules. In one way, the number of rules of the 2nd kind is reduced by reducing that of intermediate symbols. By this method, those primitive symbols precisely determined at the beginning are merged. In the other way, the length of a standard sequence of a category ex­ pressed by the right term of the rule of the 3rd kind is reduced so that portions required in classifying patterns among other categories are remained and those not essential to the contri­ bution to the classification are eliminated. By this method, some rules of the I st and 2nd kinds can be eliminated. Some patterns may be rejected even for the simple reason that a partial symbol string which does not contribute to the classification does not coincide with the same portion of the standard string, when the simplification is not conducted. When the simplification is adopted, they are correctly recognized.

## Exoeriment

An experiment to recognize Japanese spoken digits was carried out to examine the method described above.

The reasons why this method is adopted for the recognition of limited vocabulary are that by this method modified patterns by the influences of coarticulations of neighboring phonems and differences of speeds in utteran.ce can be transformed in a unified way, and more­ over, connected speech can be recognized with­ out noticing the segmentation of speech.

Data to be recognized were ten Japanese digits; /ICHI/ , / NI/ , / SAN/, / YON/ , /GO/, / ROKU/, /NANA/ , /HACHI/, /KYU/, and /REI/. Each digit was pronounced separately. The speech was analyzed and read into a com­ puter by the frequency analysis computer input system illustrated in Figure 3. Rectified filter outputs were sampled at an interval of approxi­ mately 50 ms and converted to digital signals.

As a trial to extract fundamental patterns corresponding to primitive symbols from given patterns, the mode- seeking training method similar to Bonner(I4) was applied to frequency spectrum patterns of 100 data spoken by 10 male persons, where the clusters were formed by comparing the distances of the frequency spectrum patterns.

First, by the comparison of outputs of the frequency analysis, the frequency spectrum pattern at each sampling point was classified into four major classes ; vowel, voiced conso­ nant, unvoiced consonant and stop.

Except for " stop", patterns of three classes were classified more precisely; vowels were classified into 24 classes, voiced conso­ nants into 5 classes, and unvoiced consonants 4 classes. Primitive symbols were named to these classified patterns. Table 5 shows them. As the value of the similarity between primi­ tive symbols, the Euclidean distance of the spectrum pattern was adopted. Using 100 previously used sample patterns, rules were derived by following the procedures described before for the case of the separated structure of rule,; ; the structure of symbol strings was analyzed at each category; stable symbols and key symbols were derived, and intermediate symbols and their descendants were decided based on the similarities between primitive symbols. Table 6 shows primitive symbol string of class / SAN/ . The spectrogram of the sound /SAN/ and the corresponding primitive symbols can be seen in Figure 4. Table 7 shows intermediate symbols and their descend­ ants for class / SAN/. Encircled symbol means the main descendant.

Next, primitive symbols were trans­ formed to intermediate symbols and the standard sequence was derived. Table 8 shows intermediate symbol strings and standard sequence of /SAN/ . Subsequently, rules of the 2nd and 3rd kinds were constructed. Table 9 shows them. B is the symbol which indicates the beginning of a string. X is the symbol which is not transformed by rule 1. In the rule of the 2nd kind, rules of a special kind were included : They eliminate the symbol X although the symbol X is inserted between two intermediate symbols indicated in the standard sequence. It is effective in remov­ ing a noise of the pattern while recognizing unknown input patterns.

After completely forming the rules to classify all given sample patterns first, 100 more patterns pronounced by 10 other male persons were imposed. Seventy out of them were recognized correctly, two were mis­ recognized and others were rejected. The rules were modified so that these additional patterns would be recognized correctly in accordance with the procedures described previously, and thus, the rules with which all 200 patterns could be recognized correctly were successfully established.

The same experiment was conducted also for the combined structure of rules. Rules to recognize all given patterns were composed.

Table 10 shows comparison of the number of rules in each case. The number of rules to recognize the first 100 sample patterns is shown. That for 200 patterns including 100 additional patterns is shown in parenthesis.

## Conclusion

A pattern recognizing method in refer­ ence to the rewriting rules of phrase structure grammar has been described. Patterns are transformed into a symbol string, and recog­ nized by transforming partial strings from left to right in accordance with the rules. The rules are formed in three hierarchy levels. Procedures to form and modify the rewriting rules by the use of knowledge of the symbol strings of given sample patterns and values of the similarity between symbols are described. The results of an experiment to recognize spoken Japanese digits are introduced.

It was shown that procedures described in this paper worked well for the recognition of actual patterns of spoken Japanese digits. It is thought that the number of rules to recognize ten spoken digits should be decreased. It is expected that the higher recognition rate will be accomplished by revising the primitive symbols and forming rules by collecting enough sample patterns.

In the pattern recognition by the adoption of rewriting rules, the most important factor which seriously affects result of recognition is how to decide primitive symbols, that is, how to pick up fundamental elements of the pattern. When primitive symbols which adequately re­ flect characteristics of pattern are determined, number of rules can be reduced and applicabili­ ty of the rules can be increased.

So far as the primitive symbol string of one category is not identical to that of another, these two patterns can be classified as pre­ cisely as desired by increasing length of the context. This is one of the merit of this method. As for the ability of this method to recognize unknown patterns, high recognition rate can be attained by increasing the number of sample patterns so that sample patterns thoroughly represent statistical property of patterns.

In this method, recognition cannot be made within a short period of time because rules are r efe:-red one by one. Time may be r educed by dividing rules into groups. More­ over, when a set of input symbol strings can be r egarded as regular set, it is possible to implement a machine by the use of sequential ci r cuits and recognition can be made within real time.

When the separat ed structure is com­ pared with the combined structure, number of rul e s for the combined structure is smaller. However, as long as recognition ability is con­ ce rne d, the separated structure is more advan­ tageous from the comparison of the recognition rate and number of rules· for unknown input patterns. !\loreover, as for time required in recognition, the separated structur e excel s the combined structure, if it is possible to process rule apply ing operation in parall e l for all cate ­ gories.

It is also possible to add rules of the 3rd kind inst ead of those of the 2nd kind during mod ifying rules. This means that patterns of one category can be divided into two or more cla ss e s.

Pertaining to the selection of rules, no definite criterion used to determine at which kind amongst the 1st, 2nd and 3rd kinds should the rules be modified has not yet been given, except for the increase of number of rules. However, another way is left to modify rules by using e stimated recogni tio r. rate of the rule as it can be defined.

Correct recognition can be attained by g1vmg priority to output of recognition result although the grammar is ambiguous.

The advantages of the method for recog­ n1Zlng the patterns by the use of rewriting rules in the form mentioned in this paper are that the description of the rewriting rules which ex­ press the structure of the pattern can be under­ stood easily and intuitively and that the complex patterns will be recognized at a high recognition rate.

## Acknowledgements

The authors express their deep appreci­ ation to Dr. S. Oshima and Dr. Y. Nakagome for their continual support and encouragement provided toward us for this study. The authors' thanks are also expressed to their colleagues in the Information Processing Research Group of KDD Research Laboratory for zealous discus­ sions and stimulating valuable sugg estions.

## APPENDIX

## Procedure to Decide Key Symbols

A procedure to derive key symbols from s ymbol strings of the sample patterns is intro­ duced. A relative position (R) of a s ymbol in a symbol string is defined as R=Ls / L, where Lis the length of a symbol string and Ls indicates the position of the symbol taken from the left end of the string. In this case, if two or more same symbols continue, the Ls is placed at the center of the succession. Le t the occurrence (F) be the number of strings containing a particular symbol in the symbol strings of the sample patterns. When the symbol is separated in two or more positions in a s t ring, the left­ most symbol is subjected for the examination of F. This method is called a leftmost principle.

~: The occurrence (F ) for all stable s ymbols is calculated and the symbol for which the F is highest is detected. This symbol is referred to as SM. A relat ive position of the S.M in the string containing S\1 is denoted as R(S!1.f), and the mean relative position is denoted as ~(SM), where such s ymbols as are identical with the SM the relative position of which is within a fixed value ( 0 1 ) are picked up. When the occurrence (F ) of the picked up symbol is. greater than a fixed ,·alue ( 8 2 ) , the symbol is a key symbol.

~: In the symbol strings contam1ng SM, a symbol which is located in the left of SM and the occurrence (F) of which is greater than a fixed value ( e 1) is taken in accordance with the leftmost principle. When the occurrence (F) of the symbol is greater than a fixed value ( e 1), it is denoted as SF. For a string having no SM a symbol identical with SF the relative position R(SF) of which is located within a range of a fixed value ( T1l is taken. When the occurrence (F) of SF thus counted is greater than a fixed value ( e 2)' it is a key symbol.

For symbols located to the right of the SM, the same procedure applies. This step proceeds until all symbols whose occurrences (F) are greater than a fixed value ( 6 2 ) are taken.

## References

1. T. G. Evans, "A Grammar-Controlled Pattern Analyzer", Proceedings of IFIP Congress 1968, pp. 1592-1598.
2. P. N. Sholtz, R. Bakis, "Spoken Digit Recognition Using Vowel Consonant Segmentation " , JASA, vol. 34, pp. 1-5, Jan. 1962.
3. H. Genchi, K-I. Mori, S. Watanabe, S. Katsuragi, "Recognition of Handwritten Numerical Characters for Automatic Letter Sorting", Proc. of IEEE, vol. 56, No.8, pp. 1292-1301, Aug . 1968.
4. R. Alter, "Utilization of Contextual Constraints in Automatic Speech Recog- nition", IEEE Trans., vol. AU-16, No.1, pp. 6-11, March 1968.
5. Y. Fu, "Application of Automata Theory to Automatic Speech Recognition " , Proc. of Hawaii International Conference on System Science ( 1968).
6. M. Minsky, "Steps toward Artificial Intelligence", Proc. IRE., vol. 49, No. 1, Jan. 1961.
7. R. Kirsch, "Computer Interpretation of English Text and Picture Patterns", IEEE Trans., vol. EC-13, No.4, pp. 363-376, Aug. 1964.
8. R. Narasimham, "Syntax-Directed Interpretation of Classes of Pictures", Comm. ACM, vol. 9, pp. 166-173, March 1966.
9. R. S. Ledly, L. S. Rotolo, J. B. Wilson, M. Belson, T. J. Golab and J. Jacobson, "Pattern Recognition Studies in the Bio- medical Sciences", 1966 Proc. SJCC, pp. 411-431, 1966.
10. U. Grenander, "Linguistic Tendencies Session No . 7 Pattern Recognition I General Papers ( 11) ( 12) ( 13)
11. in Pattern Analysis", IBM Scientific Center Report (1968).
12. S. Inoue, A. Kurematsu, "New Method of Recognition of Spoken Digits " , 1968 National Conference of the Institute of Electronics and Communication Engi- neers of Japan, No .
13. A. Kurematsu, M. Takeda, S. Inoue, "Pattern Recognition by Use of the Generative Grammar of the Phrase Structure Language", Technical Report of the Research Group on Automata Theory of the Institute of Electronics and Communication Engineers of Japan, A69-70, Jan. 1969.
14. N. Chomsky, "On Certain Properties of Grammars", Inform. and Control, vol. 2, pp. 137-167, 1959.
15. R. E. Bonner, "A 'Logical Pattern' Recognition Program " , IBM. J., vol. 6, pp. 353-360, 1962.