TY - CHAP
TI - Left/right deterministic linear languages identification
AU - Calera Rubio, Jorge
AU - Oncina Carratalá, Jose
DA - 2006
UR - http://hdl.handle.net/10045/8629
AB - Left deterministic linear languages are a subclass of context free languages that includes all regular languages. Recently was proposed an algorithm to identify in the limit with polynomial time and data such class of languages. It was also pointed that a symmetric class, right deterministic linear languages, is also identifiable in the limit from polynomial time and data. In this paper we show that the class of the Left-Right Deterministic Languages formed by the union of both classes is also identifiable. The resulting class is the largest one for which this type of results has been obtained so far.
In this paper we introduce the notion of n-negative characteristic sample, that is a
sample that forces an inference algorithm to output a hypothesis of size bigger than n
when strings from a non identifiable language are provided.
KW - Example-based learning
KW - Learning context-free languages
SN - 84-933652-6-2
PB - Universitat Autònoma de Barcelona. Centre de Visió per Computador
ER -