{"id":110112,"date":"2011-11-07T00:00:00","date_gmt":"2011-11-07T00:00:00","guid":{"rendered":"https:\/\/www.deberes.net\/tesis\/sin-categoria\/algoritmos-eficientes-de-estados-finitos-para-la-aplicacion-de-gramaticas-locales\/"},"modified":"2011-11-07T00:00:00","modified_gmt":"2011-11-07T00:00:00","slug":"algoritmos-eficientes-de-estados-finitos-para-la-aplicacion-de-gramaticas-locales","status":"publish","type":"post","link":"https:\/\/www.deberes.net\/tesis\/linguistica-computacional\/algoritmos-eficientes-de-estados-finitos-para-la-aplicacion-de-gramaticas-locales\/","title":{"rendered":"Algoritmos eficientes de estados finitos para la aplicaci\u00f3n de gram\u00e1ticas locales"},"content":{"rendered":"<h2>Tesis doctoral de <strong> JavierMiguel Sastre Mart\u00ednez <\/strong><\/h2>\n<p>Este trabajo se centra en la investigaci\u00f3n y el desarrollo de algoritmos eficientes de aplicaci\u00f3n de gram\u00e1ticas locales, tomando como referencia aquellos que est\u00e1n siendo usados en sistemas open-source, a saber: el analizador sint\u00e1ctico top-down de unitex y el analizador sint\u00e1ctico \u00ed\u00a0 la earley de outilex.  las gram\u00e1ticas locales son un formalismo basado en aut\u00f3matas finitos para la representaci\u00f3n de la sintaxis de los lenguajes naturales. Las gram\u00e1ticas locales son un modelo de construcci\u00f3n de descripciones precisas y a gran escala de la sintaxis de los lenguajes naturales mediante la observaci\u00f3n sistem\u00e1tica y la acumulaci\u00f3n metodol\u00f3gica de informaci\u00f3n. La idoneidad de las gram\u00e1ticas locales para esta tarea ha sido demostrada por m\u00faltiples trabajos.  debido a la naturaleza ambigua de la lengua, y a las propiedades de las gram\u00e1ticas locales, los analizadores sint\u00e1cticos cl\u00e1sicos tales como lr, el de cyk y el de tomita no son viables en el contexto de este trabajo o requieren adaptaciones no triviales. Los analizadores sint\u00e1cticos top-down y de earley son posibles alternativas, aunque tienen un coste asint\u00f3tico exponencial en el caso de las gram\u00e1ticas locales.  en primer lugar, hemos desarrollado un algoritmo de aplicaci\u00f3n de gram\u00e1ticas locales con un coste asint\u00f3tico polinomial. A continuaci\u00f3n, hemos desarrollado estructuras de datos eficientes para la gesti\u00f3n de conjuntos de elementos y de secuencias. Estas estructuras han permitido mejorar la eficiencia de nuestro algoritmo en condiciones generales. Hemos implementado dicho algoritmo y los algoritmos de unitex y outilex con las mismas herramientas con el fin de compararlos bajo las mismas condiciones. Hemos implementado distintas versiones de cada algoritmo usando nuestras estructuras de datos de tipo conjunto y aquellas incluidas en la implementaci\u00f3n de gnu de la librer\u00eda est\u00e1ndar de plantillas (standard template library o stl). Hemos comparado el rendimiento de los distintos algoritmos y de sus distintas versiones en el contexto de una aplicaci\u00f3n industrial propuesta por la empresa telef\u00f3nica i+d: aumentar la capacidad de comprensi\u00f3n de un robot conversacional capaz de suministrar servicios en l\u00ednea, tales como el env\u00edo de sms a tel\u00e9fonos m\u00f3viles as\u00ed como de juegos y de otros contenidos digitales. La comunicaci\u00f3n con el robot se realiza en espa\u00f1ol a trav\u00e9s de windows live messenger de microsoft. A pesar del dominio restringido y de la simplicidad de las gram\u00e1ticas aplicadas, los tiempos de ejecuci\u00f3n fueron menores para nuestro algoritmo y nuestras estructuras de datos de tipo conjunto. Gracias al coste asint\u00f3tico mejorado de nuestro algoritmo, son de esperar tiempos de ejecuci\u00f3n significativamente inferiores a los de los algoritmos empleados por los sistemas unitex y outilex para el caso de gram\u00e1ticas complejas y de gran cobertura.<\/p>\n<p>&nbsp;<\/p>\n<h3>Datos acad\u00e9micos de la tesis doctoral \u00ab<strong>Algoritmos eficientes de estados finitos para la aplicaci\u00f3n de gram\u00e1ticas locales<\/strong>\u00ab<\/h3>\n<ul>\n<li><strong>T\u00edtulo de la tesis:<\/strong>\u00a0 Algoritmos eficientes de estados finitos para la aplicaci\u00f3n de gram\u00e1ticas locales <\/li>\n<li><strong>Autor:<\/strong>\u00a0 JavierMiguel Sastre Mart\u00ednez <\/li>\n<li><strong>Universidad:<\/strong>\u00a0 Alicante<\/li>\n<li><strong>Fecha de lectura de la tesis:<\/strong>\u00a0 11\/07\/2011<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3>Direcci\u00f3n y tribunal<\/h3>\n<ul>\n<li><strong>Director de la tesis<\/strong>\n<ul>\n<li>\u00e9ric Laporte<\/li>\n<\/ul>\n<\/li>\n<li><strong>Tribunal<\/strong>\n<ul>\n<li>Presidente del tribunal: olivier Carton <\/li>\n<li>mikel lorenzo Forcada zubizarreta (vocal)<\/li>\n<li>\u00e9ric Laporte (vocal)<\/li>\n<li>  (vocal)<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Tesis doctoral de JavierMiguel Sastre Mart\u00ednez Este trabajo se centra en la investigaci\u00f3n y el desarrollo de algoritmos eficientes de [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"footnotes":""},"categories":[19166,16880,13880,2302,30772],"tags":[219964,219963,53901,219965],"class_list":["post-110112","post","type-post","status-publish","format-standard","hentry","category-alicante","category-construccion-de-algoritmos","category-informatica","category-linguistica-computacional","category-teoria-de-lenguajes-formales","tag-eric-laporte","tag-javiermiguel-sastre-Martinez","tag-mikel-lorenzo-forcada-zubizarreta","tag-olivier-carton"],"_links":{"self":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/110112","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/comments?post=110112"}],"version-history":[{"count":0,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/posts\/110112\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/media?parent=110112"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/categories?post=110112"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.deberes.net\/tesis\/wp-json\/wp\/v2\/tags?post=110112"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}