User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

String Extension Learning Using Lattices


Kötzing,  Timo
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Kasprzik, A., & Kötzing, T. (2010). String Extension Learning Using Lattices. In C. Martin-Vide, H. Fernau, & A. H. Dediu (Eds.), Language and Automata Theory and Applications (pp. 380-391). Berlin: Springer. doi:10.1007/978-3-642-13089-2_32.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-16F0-E
The class of regular languages is not identifiable from positive data in Gold's language learning model. Many attempts have been made to define interesting classes that \emph{are} learnable in this model, preferably with the associated learner having certain advantageous properties. Heinz '09 presents a set of language classes called \emph{String Extension (Learning) Classes}, and shows it to have several desirable properties. In the present paper, we extend the notion of String Extension Classes by basing it on \emph{lattices} and formally establish further useful properties resulting from this extension. Using lattices enables us to cover a larger range of language classes including the \emph{pattern languages}, as well as to give various ways of \emph{characterizing} String Extension Classes and its learners. We believe this paper to show that String Extension Classes are learnable in a \emph{very natural way}, and thus worthy of further study.