Identifier: TDX:2229
Authors: Martin Torres, Gabriela Susana
Abstract:
En aquest treball s'estudien aproximacions de llenguatges regulars per membres d'una varietat de llenguatges regulars donada. Es tracta d'aproximacions superiors o inferiors en el sentit de la teoria dels conjunts aproximats (Rough set theory) de Pawlak. Les relacions utilitzades per a les aproximacions són les congruències corresponents a la varietat de llenguatges regulars considerada. En particular, s'estudia l'existència de les aproximacions superior mínima i inferior màxima. En les anomenades varietats principals, aquestes sempre existeixen, i presentem algorismes per trobar-les. Per a varietats no principals, la situació és molt més complexa. En aquest cas estudiem les condicions per a la seva existència. Concretament, considerem varietats que són unió d'una família dirigida de varietats principals, i també varietats pseudo-principals, que es defineixen en aquest treball. A continuació estudiem la precisió de les aproximacions, utilitzant la densitat relativa entre el llenguatge objecte i la seva aproximació, observant després el seu comportament asimptòtic. Aquesta mesura de la precisió és aplicada a les aproximacions en les famílies de llenguatges k-definits, k-definits inversos, i,j-definits, k-testables i commutatius. Finalment examinem aproximacions sota relacions de indiscernibilitat, l'índex de les quals és infinit, seguint el treball de Paun, Polkowsky i Skowron (1997), i analitzem fins a quin punt poden ser estudiades dins del nostre marc teòric. Descrivim algunes de les seves característiques generals, comparant-les amb algunes de les famílies ja presentades, i en alguns casos, introduïm modificacions en les seves definicions per obtenir relacions de congruència. Encara que en aquesta tesi considerem sobretot varietats d’Eilenberg, les idees poden ser aplicades a altres tipus de varietats de llenguatges. El nostre treball també pot ser considerat com un abordatge al problema
Repositori URV