In 1984, Leonid Levin has initiated a theory of average-case complexity.
We provide an exposition of the basic definitions suggested by Levin,
and discuss some of the considerations underlying these definitions.
Presented is an algorithm (for learning a subclass of erasing regular
pattern languages) which
can be made to run with arbitrarily high probability of
success on extended regular languages generated by patterns
$\pi$ of the form $x_0 \alpha_1 x_1 ... \alpha_m x_m$
for unknown $m$ but known $c$,
more >>>
