Tesis computacion e informatica

Solo disponible en BuenasTareas
  • Páginas : 138 (34405 palabras )
  • Descarga(s) : 0
  • Publicado : 18 de noviembre de 2010
Leer documento completo
Vista previa del texto
PEDECIBA Inform´tica a Instituto de Computaci´n - Facultad de Ingenier´ o ıa Universidad de la Rep´blica u Montevideo, Uruguay

Tesis de Maestr´ en Inform´tica ıa a

Reglas Contextuales y Modelos de Estado Finito
Guillermo Moncecchi Diciembre de 2004

Orientadora de Tesis: Dr. Ing. Dina Wonsever Supervisora: Dr. Ing. Dina Wonsever

Resumen
Este trabajo presenta una soluci´n para laaplicaci´n simult´nea de un subo o a conjunto de reglas contextuales (un formalismo de reescritura para el an´lisis a y etiquetado de segmentos de texto), basada en t´cnicas de estado finito. Esta e soluci´n implica la definici´n de un nuevo tipo de aut´matas finitos, los transo o o ductores sobre estructuras atributo-valor y el ´lgebra de expresiones regulares a asociada a ellos. La aplicaci´n de lasreglas sobre un texto de entrada se modela o como una cascada de reemplazos basados en segmentos del texto y el contexto en que aparecen. Palabras clave: t´cnicas de estado finito, transductores, expresiones regue lares, reglas contextuales, aut´matas sobre estructuras atributo-valor. o

i

Agradecimientos
Este trabajo llev´ tiempo. Tiempo de formaci´n, tiempo de preparaci´n, o o o tiempo deelaboraci´n. Durante ese tiempo, fueron, para mi suerte, varios y o diversos quienes estuvieron ah´ ayudando, sugiriendo, apoyando. ı, La inspiraci´n para el trabajo fue un curso que dictaron hace algunos a˜os o n Dina Wonsever y Gustavo Crispino sobre tratamiento autom´tico de textos, a donde descubr´ los transductores de estado finito. Mientras tanto, el curso ı de Teor´ de Lenguajes, me permiti´acercarme a los aut´matas de todos los ıa o o tipos. Quiero agradecer a Juanjo Prada, a Diego Garat, a Marcos Campal, a Tom´s Laurenzo, y a Ernesto Copello por tomarse tan en serio su trabajo y a permitirme con ello aprender un mucho. El grupo de Lenguaje Natural del Instituto de Computaci´n me permio ti´ tener un marco donde incluir mi trabajo, y donde darle aplicaci´n. En este o o tiempo, la gu´de Dina fue fundamental para evolucionar hacia el resultado ıa final. Las sugerencias de todo el equipo para mejorar lo hecho, tambi´n. La e amabilidad de Ken Beesley para aclararme tantas dudas sobre relaciones regulares, transductores o lo que fuera, me allanaron varias veces el camino. A todos mi m´s sincero agradecimiento. a Este trabajo est´ dedicado a Ver´nica, la primera, y a mi familia,por a o razones obvias.

ii

´ Indice general
1. Introducci´n o 2. Reglas Contextuales: el problema de su aplicaci´n o 2.1. El formalismo de reglas contextuales . . . . . . . . . . . . . . . 2.2. Un int´rprete de reglas . . . . . . . . . . . . . . . . . . . . . . . e 2.3. Un subconjunto de las reglas contextuales y el problema . . . . 3. Marco Te´rico o 3.1. T´cnicas de Estado Finito . . . . .. . . . . . . . e 3.1.1. Aut´matas Finitos y Lenguajes Regulares o 3.1.2. Transductores y Relaciones Regulares . . . 3.1.3. Aut´matas aumentados con predicados . . o 3.1.4. Estado del arte . . . . . . . . . . . . . . . 3.2. Estructuras Atributo-Valor . . . . . . . . . . . . . 3.2.1. Definici´n . . . . . . . . . . . . . . . . . . o 3.2.2. Subsumci´n y Unificaci´n . . . . . . . . . o o . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 4 4 5 7 8 8 8 11 21 27 28 28 28 30 31 31 36 41 44 45 47 49 50 51 51 51 53

4. Un modelo para la aplicaci´n de reglas contextuales o 4.1. Aut´matas sobreestructuras atributo-valor . . . . . . . o 4.1.1. Definici´n . . . . . . . . . . . . . . . . . . . . . o 4.1.2. fs-aut´matas como pfsr . . . . . . . . . . . . . . o 4.1.3. fs-transductores y fs-pfst . . . . . . . . . . . . . ´ 4.1.4. Algebra modificada de expresiones regulares . . 4.2. Una aproximaci´n inicial a la soluci´n . . . . . . . . . o o 4.3. Aplicaci´n simult´nea de reglas . . . . . . ....
tracking img