## An Average-Case Optimal One-Variable Pattern Language LearnerAuthors: Rüdiger Reischuk
^{*}
and Thomas ZeugmannSource: Electronic Colloquium on Computational Complexity, Report TR98-069, December 08, 1998.
For almost all meaningful distributions
defining how the pattern variable is replaced by a string to generate
random examples of the target pattern language,
it is shown that this algorithm converges within an
Though one-variable pattern languages can neither be finitely inferred
from positive data nor PAC-learned,
our approach can also be extended to a It is a long standing open problem whether pattern languages can be learned in case that substitutions of pattern variables by the empty string can also occur. Our learning strategy can be generalized to this situation as well. Finally, we show some experimental results for the behavior of this new learning algorithm in practice.
^{*}This work was performed while this author
was visiting the Department of Informatics at Kyushu University and was supported
by the Japanese Society for the Promotion of Science under Grant
JSPS 29716102.
Note that we have implemented the learning algorithms presented in this paper, and you may try them out using our Average Case Optimal 1-Variable Pattern Language Learning page which is also mirrored in Japan. |