Left/right deterministic linear languages identification

Empreu sempre aquest identificador per citar o enllaçar aquest ítem http://hdl.handle.net/10045/8629
Información del item - Informació de l'item - Item information
Títol: Left/right deterministic linear languages identification
Autors: Calera Rubio, Jorge | Oncina Carratalá, Jose
Grups d'investigació o GITE: Reconocimiento de Formas e Inteligencia Artificial
Centre, Departament o Servei: Universidad de Alicante. Departamento de Lenguajes y Sistemas Informáticos
Paraules clau: Example-based learning | Learning context-free languages
Àrees de coneixement: Lenguajes y Sistemas Informáticos
Data de publicació: 2006
Editor: Universitat Autònoma de Barcelona. Centre de Visió per Computador
Citació bibliogràfica: CALERA RUBIO, Jorge; ONCINA CARRATALÁ, Jose. "Left/right deterministic linear languages identification". En: Pattern recognition: progress, directions and applications / edited by Filiberto Pla, Petia Radeva and Jordi Vitrià. Barcelona : Centre de Visió per Computador, Universitat Autònoma de Barcelona, 2006. ISBN 84-933652-6-2, pp. 313-326
Resum: 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.
Patrocinadors: Work partially supported by Spanish CICyT though project TIC2003-08496-C04 and by the IST Programme of the European Community, under the Pascal Network of Excellence, IST-2002-506778.
URI: http://hdl.handle.net/10045/8629
ISBN: 84-933652-6-2
Idioma: eng
Tipus: info:eu-repo/semantics/bookPart
Revisió científica: si
Apareix a la col·lecció: INV - GRFIA - Capítulos de Libros

Arxius per aquest ítem:
Arxius per aquest ítem:
Arxiu Descripció Tamany Format  
Thumbnail1_-_calera_oncina.pdf278,03 kBAdobe PDFObrir Vista prèvia


Tots els documents dipositats a RUA estan protegits per drets d'autors. Alguns drets reservats.