Three Learnable Models for the Description of Language

Research output: Chapter in Book/Report/Conference proceedingOther chapter contribution

9 Citations (Scopus)


Learnability is a vital property of formal grammars: representation classes should be defined in such a way that they are learnable. One way to build learnable representations is by making them objective or empiricist: the structure of the representation should be based on the structure of the language. Rather than defining a function from representation to language we should start by defining a function from the language to the representation: following this strategy gives classes of representations that are easy to learn. We illustrate this approach with three classes, defined in analogy to the lowest three levels of the Chomsky hierarchy. First, we recall the canonical deterministic finite automaton, where the states of the automaton correspond to the right congruence classes of the language. Secondly, we define context free grammars where the non-terminals of the grammar correspond to the syntactic congruence classes, and where the productions are defined by the syntactic monoid; finally we define a residuated lattice structure from the Galois connection between strings and contexts, which we call the syntactic concept lattice, and base a representation on this, which allows us to define a class of languages that includes some non-context free languages, many context-free languages and all regular languages. All three classes are efficiently learnable under suitable learning paradigms.
Original languageEnglish
Title of host publicationLanguage and Automata Theory and Applications
Subtitle of host publication4th International Conference, LATA 2010, Trier, Germany, May 24-28, 2010. Proceedings
EditorsAdrian-Horia Dediu, Henning Fernau, Carlos Martín-Vide
PublisherSpringer Berlin Heidelberg
Number of pages16
ISBN (Electronic)978-3-642-13089-2
ISBN (Print)978-3-642-13088-5
Publication statusPublished - 2010

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Dive into the research topics of 'Three Learnable Models for the Description of Language'. Together they form a unique fingerprint.

Cite this