In the field of grammatical inference, the goal of any learning algorithm is to identify a target concept from a given class by having access to a specific type of information. The main learning settings are Gold's model of learning in the limit and Angluin's query learning. This dissertation is primarily concerned with the second approach.We thoroughly investigate a recently introduced, linguistic motivated, type of query called Correction Query (CQ). We consider three possible definitions, and for each of them we give necessary and sufficient conditions for a language class to be learnable with these types of queries. Furthermore, we compare the model of learning with CQs with other well-known Gold-style and query learning models when no efficiency constraints are imposed. Results are also obtained for the restricted version of the model of learning with CQs in polynomial time. Additionally, we discuss the learnability of deterministic finite automata (DFAs) with correction and equivalence queries. We design several learning algorithms and we present a comparison between our algorithms and the standard algorithm for learning DFAs with membership and equivalence queries. These results are furthermore extended from string languages to tree languages. / Dentro del ámbito de la inferencia gramatical, el objetivo de cualquier algoritmo de aprendizaje consiste en identificar un concepto de una clase dada, teniendo acceso a un tipo específico de información. Los dos modelos de aprendizaje principales son: el modelo de aprendizaje en el límite propuesto por Gold y el modelo de aprendizaje a partir de preguntas de Angluin. Esta tesis se centra fundamentalmente en el segundo tipo de aprendizaje. En esta tesis doctoral investigamos a fondo un tipo de preguntas introducidas recientemente, por motivos lingüísticos, denominada PREGUNTA DE CORRECCIÓN. Nosotros consideramos tres posibles definiciones, y para cada uno de ellos presentamos condiciones necesarias y suficientes para que una clase de lenguajes sea identificable con estos tipos de preguntas. Además, comparamos estos tres modelos de aprendizaje a partir de preguntas de corrección con otros modelos de aprendizaje, en el caso general (sin ninguna restricción de tiempo) y también imponiendo que los algoritmos sean polinómicos.Además, investigamos el aprendizaje de autómata finitos deterministas (AFD) con preguntas de corrección y equivalencia. Diseñamos varios algoritmos de aprendizaje y presentamos una comparación entre nuestros algoritmos y el algoritmo estándar de aprendizaje a partir de preguntas de pertenencia y equivalencia. Estos resultados son, además, extendidos para los lenguajes de árboles.
| Identifer | oai:union.ndltd.org:TDX_URV/oai:www.tdx.cat:10803/8792 |
| Date | 09 January 2009 |
| Creators | Tirnauca, Cristina |
| Contributors | Mitrana, Victor, Higuera, Colin de, Bel Enguix, Gemma, Universitat Rovira i Virgili. Departament de Filologies Romàniques |
| Publisher | Universitat Rovira i Virgili |
| Source Sets | Universitat Rovira i Virgili |
| Language | English |
| Detected Language | Spanish |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs., info:eu-repo/semantics/openAccess |
Page generated in 0.0017 seconds