- -

Autómatas finitos: irreducibilidad e Inferencia

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

Autómatas finitos: irreducibilidad e Inferencia

Mostrar el registro sencillo del ítem

Ficheros en el ítem

dc.contributor.advisor García Gómez, Pedro es_ES
dc.contributor.author Vázquez-De-Parga Andrade, Manuel es_ES
dc.date.accessioned 2008-06-20T07:30:35Z
dc.date.available 2008-06-20T07:30:35Z
dc.date.created 2008-05-21T08:00:00Z es_ES
dc.date.issued 2008-06-20T07:30:24Z es_ES
dc.identifier.uri http://hdl.handle.net/10251/2321
dc.description.abstract En este trabajo abordamos dos problemas: El de la reducción de autómatas finitos y el de la inferencia de los lenguajes regulares y estudiamos las relaciones entre ellos. Tras la introducción, en el segundo capítulo se repasan los conceptos y proposiciones básicos de teoría de lenguajes y se establece la notación utilizada a lo largo del trabajo. Lo mismo, pero en lo que concierne a la inferencia gramatical, se realiza en el tercer capítulo, donde se describe además el actual estado del arte. En el cuarto capítulo se discuten los problemas de minimalización y reducción de autómatas finitos y se demuestra el primero de los resultados centrales de esta tesis, la existencia de una cota en el tamaño de los autómatas finitos irreducibles que aceptan un determinado lenguaje regular. Se introducen además los conceptos de irreducibilidad y concisión relativas. En el capítulo quinto se discuten y amplían los conceptos de red de autómatas cocientes y completitud estructural y se introduce el concepto de universalidad estructural. Como resultado de este estudio se obtiene el segundo de los resultados centrales de este trabajo, el cual establece que cualquier algoritmo de fusión de estados que obtenga como resultado un autómata finito irreducible compatible con los datos de entrada infiere en el límite la clase de los lenguajes regulares siempre y cuando se aplique en cierta manera, por lo demás poco restrictiva. En el capítulo sexto se introduce el concepto de subautómata asociado a una palabra en un lenguaje y a partir de él se describe una nueva familia de algoritmos de inferencia de la clase de los lenguajes regulares representados mediante autómatas finitos, algoritmos que tienen la particularidad de que su complejidad temporal es función básicamente de la longitud de las palabras de la muestra de entrada, mientras que son prácticamente lineales respecto al número de las mismas. En el capítulo séptimo se describen algunos algorítmos de las familias menci es_ES
dc.language Español es_ES
dc.publisher Universitat Politècnica de València es_ES
dc.rights Reserva de todos los derechos es_ES
dc.source Riunet
dc.subject Autómatas finitos es_ES
dc.subject Inferencia gramatical es_ES
dc.subject No determinismo es_ES
dc.subject Reducibilidad es_ES
dc.title Autómatas finitos: irreducibilidad e Inferencia
dc.type Tesis doctoral es_ES
dc.subject.unesco 120304 - Inteligencia artificial es_ES
dc.subject.unesco 110204 - Lenguajes formalizados es_ES
dc.identifier.doi 10.4995/Thesis/10251/2321 es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Sistemas Informáticos y Computación - Departament de Sistemes Informàtics i Computació es_ES
dc.description.bibliographicCitation Vázquez-De-Parga Andrade, M. (2008). Autómatas finitos: irreducibilidad e Inferencia [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/2321 es_ES
dc.description.accrualMethod Palancia es_ES
dc.type.version info:eu-repo/semantics/acceptedVersion es_ES
dc.relation.tesis 2801 es_ES


Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem