Esta investigación aborda el tema del diseño de algoritmos de inferencia gramatical para lenguajes regulares, particularmente en lo relacionado con la mezcla de estados como elemento fundamental del proceso de inferencia. Se estudia la mezcla de estados en sus variantes determinista y no determinista desde el punto de vista teórico. Como resultado se propone una manera eficiente de realizar la mezcla de estados no determinista y se demuestra que la inferencia gramatical de lenguajes regulares basada en la mezcla de estados (tanto determinista como no determinista) converge en el límite independientemente del orden en que se realizan las mezclas. La demostración es de interés ya que entre otras consecuencias, permite afirmar la convergencia en el límite de la estrategia EDSM (Evidence Driven States Merging) que es ampliamente conocida en la literatura como un heurísico. Dado que la demostración considera también la inferencia de autómatas no deterministas, el resultado abre la puerta al desarrollo de algoritmos convergentes que infieren autómatas no deterministas. El aspecto experimental de esta investigación propone un conjunto de algoritmos de inferencia gramatical para lenguajes regulares, todos ellos convergentes en el límite. Estos algoritmos surgen de aplicar diferentes variantes de mezcla de estados determinista y no determinista; ellos buscan aprovechar la información que se puede obtener a partir de las relaciones de inclusión entre los lenguajes por la derecha asociados a los estados de todo autómata. Se proponen cuatro algoritmos que hacen mezcla determinista y dos que hacen mezcla no determinista de estados. Los resultados obtenidos al comparar estos nuevos algoritmos con algoritmos de referencia como RPNI, red-blue o DeLeTe2 muestran que se logra disminuir significativamente el tamaño de las hipótesis que se producen, al tiempo que se consiguen tasas de reconocimiento comparables o ligeramente inferiores. También se han obtenido algunas mejoras en la co / Álvarez Vargas, GI. (2007). Estudio de la mezcla de estados determinista y no determinista en el diseño de algoritmos para inferencia gramatical de lenguajes regulares [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/1957

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 / 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

Se recopiló una base de datos geográfica, con cartografía básica y temática, sobre la provincia de Napo (Ecuador), en la que se destacan los mapas de cobertura del suelo de los años 2002 y 2008. Como primer producto se elaboró un mapa de cobertura del suelo del año 1990 a partir de imágenes del sensor TM, (Landsat 4 y 5). Posteriormente se realizó un modelo de probabilidad de presencia de coberturas de tipo antrópico, usando la técnica de regresión logística multivariada; se evaluó el modelo con la curva ROC (Relative Operating Characteristic) y se determinó un alto poder de predicción en el modelo (AUC 0.89), distinguiendo además, que la distancia a centros poblados y a vías de comunicación son las variables más influyentes para la presencia de coberturas antrópicas. Se utilizó el mapa resultante del modelo de probabilidad como entrada en un modelo de transición de coberturas que combina Autómatas Celulares y Cadenas de Markov, entre otros aspectos, simulando un mapa de tipo de coberturas (natural o antrópico) para el año 2008. Se evaluó este mapa simulado, comparándolo con uno de referencia, a partir de índices kappa, y se obtuvo un porcentaje de concordancia general de 93%, lo cual es un buen indicador. Una vez que se ha contado con un modelo que permitía hacer simulaciones con el grado de confianza necesario, se realizaron simulaciones para los años 2015 y 2020. En estos escenarios de tipo de cobertura, se puede ver una clara presión hacia los bosques de la rivera del Rio Napo en un futuro, y también en aquellos cercanos a los principales centros poblados como Tena especialmente. Sin embargo, las áreas protegidas muestran un estado de conservación “natural” en las simulaciones, y esto se debe a sus condiciones de inaccesibilidad, en cuanto a falta de infraestructura vial, y a sus condiciones ambientales especiales. Por último, se verificó que la tasa de deforestación (cambio de natural hacia antrópico) en el período 1990-2008 fue de 4661 ha/año y en el período 2008-2020 sería de 3550 ha/año, indicando que la tendencia en el tiempo muestra en el mejor de los casos una disminución o por lo menos una estabilización de los procesos de deforestación.

Uno de los problemas más importantes en los sistemas de realidad virtual es la diversidad de los dispositivos visuales y de interacción que existen en la actualidad. Junto a esto, la heterogeneidad de los motores gráficos, los motores físicos y los motores de inteligencia artificial, propicia que no exista un modelo que aúne todos estos aspectos de una forma integral y coherente. Con el objetivo de unificar toda esta diversidad, presentamos un modelo formal que afronta de forma integral el problema de la diversidad en los sistemas de realidad virtual, así como la definición de los módulos principales que los constituyen. El modelo propuesto se basa en la definición de varias gramáticas que integra su actividad, su visualización y su interacción con el usuario. La descripción de un mundo se presenta como una cadena de un lenguaje L(M) que representa una secuencia ordenada de agentes que aceptan eventos y que definen la actividad del sistema. Por otro lado, la visualización del estado actual del sistema se traduce en otra cadena del lenguaje de visualización L(V) y que está compuesta de primitivas y transformaciones. Los conceptos de primitiva y transformación son mucho más amplios de lo que es habitual en estos sistemas. Las primitivas no son simples primitivas de dibujo sino acciones que se deben ejecutar en un determinado sistema de representación que es definida mediante otro lenguaje L(G) y que representa las acciones ordenadas en un determinado dispositivo visual o no. Las transformaciones, por otro lado, modifican las primitivas, dependiendo de su naturaleza. Los agentes desarrollan una o varias actividades en el mundo virtual, se visualizan mediante primitivas y transformaciones, y usan eventos que también se definen en sentido amplio. El modelo presentado tiene como virtud la separación de la actividad del sistema de los dispositivos visuales y de interacción concretos que lo componen. Esto supone varias ventajas: los dispositivos pueden ser sustituidos por otros dispositivos o por simulaciones de estos, los elementos del sistema pueden ser reutilizados, y la representación gráfica puede ser diferente dependiendo del dispositivo visual. En definitiva, se ha pretendido diseñar un sistema integral, adaptativo, reutilizable y genérico. Por último, se presentan varios casos prácticos que permiten concretar cómo se utiliza el modelo propuesto.

[EN] In this thesis a real application related to the string correction process from an OCR classifier in a form digitizing task is presented. These strings come from a classifier with a given error ratio that implies that some characters in the string have been potentially misclassified, producing erroneous words. This raises the need to introduce some kind of postprocess to improve the strings. The implementation of such postprocess takes into account all the available evidence in a given moment. In the case proposed here, these evidences are the charactersrecognized by the classifier with their posterior probabilities, the confusion matrix between symbols and the language model finally accepted. Each evidence is modelled independently by means of a WFST and then combined by means of the composition operation into a single integrated automata. From this automata, the path that maximizes the probability is selected. This path is the string, that belongs to the language model, that is the nearest string to the OCR hypothesis according to the confusion matrix. The final system offers two different results: on the one hand the corrected string, on the other hand the transformation cost produced during the string correction. Additionally, it is proposed a general method of error estimation using the input string transformation cost that establishes a threshold in terms of the cost and the proposed end-user parameter: the acceptable final error. This thesis presents a method for estimating adaptive rejection threshold estimation that allows for a certain percentage of error in a lot of strings from one language (sample) that presents several advantages. On the one hand, it is independent from transformation cost postprocessing distribution of such samples. On the other hand, it allows the user to set the threshold for a familiar and advantageous manner, as is setting the desired rate of sampling error. For this, first, and for a given language, a model that estimates the probability of error associated with the acceptation of postprocessed strings with a given transformation cost is defined. Then, the procedure that performs the rejection threshold estimation adaptively in order to achieve predefined rate error for a test batch is presented. In addition, an approach to obtain the above model is proposed when there are no real and supervised OCR hypothesis in the learning stage. The chapter is accompanied by experiments whose results demonstrate the utility of the proposed method. Next, linking in somehow with the search for an increased productivity in a possible string validation task, of previously strings rejected by the system through the foregoing error estimation method, a method of multimodal and interactive human-computer interaction that composes the above information with the prefix introduced by the user, while the validation process occurs, making use, for this, of WFST and the automata composition operation. The search for the most likely string for each new interaction offered by the user, in the composed automata, presented here, shows a clear increase in productivity by requiring fewer keystrokes in obtaining the correct string. Finally, a tolerant fault multimodal and interactive interface, using also WFST, is shown by making the composition of different information sources together with an error model related with the possible confusion caused due to the arrangement of keys on a keyboard. The application shown in this case is related to the introduction of a destination into a GPS device where is considered both the information related to the next destinations to a specific place, such as the information related to the entered prefix and errors that may occur due to the arrangement of keys on the input device considered. / [ES] En esta tesis se presenta inicialmente una aplicación real de corrección de cadenas procedentes de un clasificador OCR en una tarea de digitalización de formularios. Estas cadenas, proceden de un clasificador con cierta probabilidad de error, lo que implica la posibilidad de que alguno de los caracteres pertenecientes a una palabra sea erróneo, produciendo finalmente palabras incorrectas. Esto plantea la necesidad de introducir algún tipo de postproceso que mejore dichas cadenas. Para implementar dicho postproceso, se tienen en cuenta todas las evidencias disponibles en un momento dado. En el caso propuesto aquí serán los caracteres reconocidos por el propio clasificador con su probabilidad a posteriori, la matriz de confusión entre símbolos y el modelo de lenguaje finalmente aceptado. Cada una de estas evidencias se modela de manera independiente en forma de un WFST. Una vez modeladas se fusionan mediante la operación de composición de autómatas en un único autómata integrado. A partir de este autómata, se selecciona el camino que maximiza la probabilidad y que corresponde con la cadena perteneciente al lenguaje más cercana a la hipótesis OCR según la matriz de confusión entre símbolos. El sistema final ofrecerá dos resultados diferentes: por una parte la cadena corregida y por otra el coste de transformación de dicha corrección. Por otra parte, se plantea un método general de estimación del error frente a un coste de transformación de las cadenas de entrada que permite establecer un umbral dinámico en función de dicho coste y un parámetro propuesto por el usuario final: el error final asumible. Para ello en esta tesis se presenta un método adaptativo de estimación del umbral de rechazo que permite estimarlo para obtener un determinado porcentaje de error en un lote de cadenas de un lenguaje (muestra) que presenta diversas ventajas. Por un lado, es independiente de la distribución de los costes de transformación de dichas muestras. Por otro lado, permite al usuario establecer el umbral de una manera familiar y ventajosa, como es fijando la tasa de error deseada de la muestra. Para todo ello, en primer lugar, y para un lenguaje dado, se define un modelo que estima la probabilidad de error asociada a aceptar cadenas con un coste de transformación determinado. A continuación, se expone el procedimiento que lleva a cabo la estimación del umbral de rechazo de manera adaptativa con el objetivo de alcanzar la tasa de error predefinida para un lote de test. Además, se propone una aproximación para la obtención del modelo anterior cuando no se dispone de hipótesis OCR reales y supervisadas en la etapa de aprendizaje. Seguidamente y enlazando en cierta forma con la búsqueda de un incremento de productividad en una posible validación de las cadenas, previamente rechazadas por el sistema a través del método de estimación del error anteriormente expuesto, se presenta un método de interacción persona-máquina multimodal e interactivo que fusiona la información anterior junto al prefijo introducido, por el propio usuario, durante dicho proceso de validación, haciendo uso para ello de los WFST y la operación de composición de autómatas. Para finalizar, se muestra otra interfaz multimodal e interactiva tolerante a fallos, mediante la fusión de diferentes fuentes de información junto a un modelo de error relacionado con las posibles confusiones producidas debido a la disposición de las teclas de un teclado. Para ello, se hace uso también de WFST para su modelado. La aplicación mostrada en este caso está relacionada con la introducción de un destino en un dispositivo GPS y en ella se considera, tanto la información de los destinos próximos a un lugar concreto, como la información relativa al prefijo introducido y los errores que pueden aparecer debido a la propia disposición de las teclas en el dispositivo de entrada. / [CA] En aquesta tesi es presenta inicialment una aplicació real de correcció de cadenes procedents d'un classificador OCR en una tasca de digitalització de formularis. Aquestes cadenes, procedeixen d'un classificador amb una determinada probabilitat d'error, la qual cosa implica la possibilitat de que algun dels caràcters que pertanyen a una paraula siga erroni, produint finalment paraules incorrectes. Això planteja la necessitat d'introduir algun tipus de postprocés que millore aquestes cadenes. Per implementar aquest postprocés, es tenen en compte totes les evidències disponibles en un moment donat. En el cas proposat ací, seran els caràcters reconeguts pel propi classificador amb la seua probabilitat a posteriori, la matriu de confusió entre símbols i el model de llenguatge finalment acceptat. Cadascuna d'aquestes evidències es modela de manera independent en forma d'un WFST. Una vegada modelades es fusionen mitjançant l'operació de composició d'autòmats en un únic autòmat integrat. A partir d'aquest autòmat, es selecciona el camí que fa màxima la probabilitat i que es correspon amb la cadena més propera a la hipòtesi OCR que pertany al llenguatge segons la matriu de confusió entre símbols. El sistema final oferirà dos resultats diferents: d'una banda la cadena corregida, i d'una altra, el cost de transformació d'aquesta correcció. D'una altra banda, es planteja un mètode general d'estimació de l'error front al cost de transformació de les cadenes d'entrada que permet establir un llindar dinàmic en funció d'aquest cost i un paràmetre proposat per l'usuari final: l'error final assumible. Per això en aquesta tesi es presenta un mètode adaptatiu d'estimació de rebuig, amb la finalitat d'obtindre un determinat percentatge d'error en un lot de cadenes d'un llenguatge (mostra) que presenta diversos avantatges. D'una banda és independent de la distribució dels costos de transformació de les mostres esmentades. D'altra banda, permet l'usuari establir el llindar d'una manera familiar i avantatjosa, com és fixant la tasa d'error desitjada per la mostra. Per tot això, en primer lloc, i donat un llenguatge, es defineix un model que estima la probabilitat d'error associada a acceptar cadenes amb un cost de transformació determinat. A continuació, s'exposa el procediment que du a terme l'estimació del llindar de rebuig de manera adaptativa amb l'objectiu de arribar a la tasa d'error predefinida per a un lot de test. A més a més, es proposa una aproximació per a obtindre el model anterior quant no es disposa d'hipòtesi OCR reals i supervisades a l'etapa d'aprenentatge. Seguidament, i enllaçant amb la recerca d'un increment en la productivitat en una possible validació de cadenes prèviament rebutjades pel sistema a través del mètode d'estimació de l'error anteriorment exposat, es presenta un mètode d'interacció persona-màquina multimodal i interactiu que fusiona la informació anterior, juntament amb el prefix introduït pel propi usuari durant l'esmentat procés de validació, fent ús dels WFST i l'operació de composició d'autòmats. La recerca de la cadena més probable, en cada nova interacció oferida per l'usuari ens mostra un clar increment de la productivitat, al requerir un nombre menor de pulsacions de teclat per obtindre la cadena correcta. Per finalitzar, es mostra una altra interfície multimodal i interactiva tolerant a errades, mitjançant la fusió de diferents fonts d'informació juntament a un model d'error relacionat amb les possibles confusions produïdes a causa de la disposició de les lletres d'un teclat. En aquest cas es fa ús també dels WFST en el seu modelat. L'aplicació mostrada en aquest cas està relacionada amb la introducció d'una destinació en un dispositiu GPS i en aquesta es considera tant la informació pròxima a un lloc concret, com la informació relativa al prefix introduït, junt als errors que poden aparèixer a causa de la pròpia dispos / Navarro Cerdán, JR. (2016). Aplicaciones de los autómatas transductores finitos con pesos (WFST) en la corrección simbólica en interfaces persona-máquina [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/62688

Els paradigmes cel·lulars, com les xarxes neuronals cel·lulars (CNN, en anglès) i els autòmats cel·lulars (CA, en anglès), són una eina excel·lent de càlcul, al ser equivalents a una màquina universal de Turing. La introducció de la màquina universal CNN (CNN-UM, en anglès) ha permès desenvolupar hardware, el nucli computacional del qual funciona segons la filosofia cel·lular; aquest hardware ha trobat aplicació en diversos camps al llarg de la darrera dècada. Malgrat això, encara hi ha moltes preguntes a obertes sobre com definir els algoritmes d'una CNN-UM i com estudiar la dinàmica dels autòmats cel·lulars. En aquesta tesis es tracten els dos problemes: primer, es demostra que es possible acotar l'espai dels algoritmes per a la CNN-UM i explorar-lo gràcies a les tècniques genètiques; i segon, s'expliquen els fonaments de l'estudi dels CA per mitjà de la dinàmica no lineal (segons la definició de Chua) i s'il·lustra com aquesta tècnica ha permès trobar resultats innovadors. / Los paradigmas celulares, como las redes neuronales celulares (CNN, eninglés) y los autómatas celulares (CA, en inglés), son una excelenteherramienta de cálculo, al ser equivalentes a una maquina universal deTuring. La introducción de la maquina universal CNN (CNN-UM, eninglés) ha permitido desarrollar hardware cuyo núcleo computacionalfunciona según la filosofía celular; dicho hardware ha encontradoaplicación en varios campos a lo largo de la ultima década. Sinembargo, hay aun muchas preguntas abiertas sobre como definir losalgoritmos de una CNN-UM y como estudiar la dinámica de los autómatascelular. En esta tesis se tratan ambos problemas: primero se demuestraque es posible acotar el espacio de los algoritmos para la CNN-UM yexplorarlo gracias a técnicas genéticas; segundo, se explican losfundamentos del estudio de los CA por medio de la dinámica no lineal(según la definición de Chua) y se ilustra como esta técnica hapermitido encontrar resultados novedosos. / Cellular paradigms, like Cellular Neural Networks (CNNs) and Cellular Automata (CA) are an excellent tool to perform computation, since they are equivalent to a Universal Turing machine. The introduction of the Cellular Neural Network - Universal Machine (CNN-UM) allowed us to develop hardware whose computational core works according to the principles of cellular paradigms; such a hardware has found application in a number of fields throughout the last decade. Nevertheless, there are still many open questions about how to define algorithms for a CNN-UM, and how to study the dynamics of Cellular Automata. In this dissertation both problems are tackled: first, we prove that it is possible to bound the space of all algorithms of CNN-UM and explore it through genetic techniques; second, we explain the fundamentals of the nonlinear perspective of CA (according to Chua's definition), and we illustrate how this technique has allowed us to find novel results.