Learning One-Variable Pattern Languages in Linear Average TimeAuthors: Rüdiger Reischuk* and Thomas Zeugmann Source: DOI-Technical Report DOI-TR 140, Department of Informatics, Kyushu University, Fukuoka, Japan, September 1997. Abstract. A new algorithm for learning one-variable pattern languages is proposed and analysed with respect to its average-case behaviour. We consider the total learning time that takes into account all operations till an algorithm has converged to a correct hypothesis. For the expectation it is shown that for almost all meaningful distributions defining how the pattern variable is replaced by a string to generate random samples of the target pattern language this algorithm converges within a constant number of rounds with a total learning time that is linear in the pattern length. Thus, the algorithm is average-case optimal in a strong sense.
*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. |