Teoremas de punto fijo para la solución de ecuaciones sobre lenguajes

Abstract

En este trabajo se aborda el estudio de teoremas de punto fijo sobre retículos completos con el fin de ser aplicados a una clase de funciones entre lenguajes, llamadas funciones polinomiales. Estas funciones permiten caracterizar los lenguajes regulares y los independientes de contexto como una componente del menor punto fijo de una determinada función polinomial. Además, permiten solucionar algunas ecuaciones sobre lenguajes, en particular se demuestra el lema de Arden y una generalización de éste, lo cual permitirá caracterizar algunos lenguajes lineales. / Abstract. In this work we study fixed-point theorem on complete lattices to be applied to a class of functions between languages, called polynomial functions. These functions allow characterization of regular languages and context-free languages as one component of the minor fixed point of a given polynomial function. Also, would solve some languages equations, in particular proves the Arden’s lemma and a generalization of it, which will characterize some linear languages.