The previous literature gave a number of algorithms for generalizing to SOREs providing a trade off between generalization speed and quality of the solution. Furthermore, a fast but non-optimal algorithm for generalizing to CHAREs is known.
For each of the two language classes we give an efficient algorithm returning a minimal generalization from the given finite sample to an element of the fixed language class; such generalizations are called descriptive. In this sense, both our algorithms are optimal.