ON THE RELATIONSHIP BETWEEN DIAGRAM SYNTHESIS AND GRAMMATICAL INFERENCE

Biermann's algorithm for synthesizing state diagrams is reformulated b y using standard concepts of grammatical inference. For each instance of the diagram synthesis problem we define an instance of a grammatica l inference problem. A restricted case of the diagram synthesis proble m is introduced in order to find such a special case in which the corr esponding language inference problem can be efficiently solved by usin g positive data only.