E. Makinen, ON THE RELATIONSHIP BETWEEN DIAGRAM SYNTHESIS AND GRAMMATICAL INFERENCE, International journal of computer mathematics, 52(3-4), 1994, pp. 129-137
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.