Rough approximations in varieties of regular languages

dc.contributor
Universitat Rovira i Virgili. Departament de Filologies Romàniques
dc.contributor.author
Martin Torres, Gabriela Susana
dc.date.accessioned
2016-05-04T10:33:36Z
dc.date.available
2016-05-04T10:33:36Z
dc.date.issued
2016-02-01
dc.identifier.uri
http://hdl.handle.net/10803/379823
dc.description.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
cat
dc.description.abstract
En este trabajo se estudian aproximaciones de lenguajes regulares por miembros de una variedad de lenguajes regulares dada. Se trata de aproximaciones superiores o inferiores en el sentido de la teoría de los conjuntos approximados (Rough set theory) de Pawlak. Las relaciones utilizadas para las aproximaciones son las congruencias correspondientes a la variedad de lenguages regulares considerada. En particular, se estudia la existencia de las aproximaciones superior mínima e inferior máxima. En las llamadas variedades principales, éstas siempre existen, y presentamos algoritmos para hallarlas. Para variedades no principales, la situación es mucho más compleja. En este caso estudiamos las condiciones para su existencia. Concretamente, consideramos variedades que son unión de una familia dirigida de variedades principales, y también variedades pseudo-principales, que se definen en este trabajo. A continuación estudiamos la precisión de las aproximaciones, utilizando la densidad relativa entre el lenguaje objeto y su aproximación, observando luego su comportamiento asintótico. Esta medida de la precisión es aplicada a las aproximaciones en las familias de lenguajes k-definidos, k-definidos inversos, i,j-definidos, k-testables y conmutativos. Finalmente examinamos aproximaciones bajo relaciones de indiscernibilidad, cuyo índice es infinito, siguiendo el trabajo de Paun, Polkowsky y Skowron (1997), y analizamos hasta qué punto pueden ser estudiadas dentro de nuestro marco teórico. Describimos algunas de sus características generales, comparándolas con algunas de las familias ya presentadas, y en algunos casos, introducimos modificaciones en sus definiciones para obtener relaciones de congruencia. Aunque en esta tesis consideramos sobre todo variedades de Eilenberg, las ideas pueden ser aplicadas a otros tipos de variedades de lenguajes. Nuestro trabajo también puede ser considerado como un abordaje al problema de la inferencia caracterizable, en la cual a partir de una muestra, se infiere un lenguaje de un tipo determinado.
spa
dc.description.abstract
We study approximations of regular languages by members of a given variety of regular languages. These are upper or lower approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given variety of regular languages. In particular, we consider the closest upper and lower approximations in the later. In the so-called principal varieties these always exist, and we present algorithms for finding them, but for other varieties the situation is more complex. For non-principal +-varieties we study conditions for the existence of the closest upper and lower approximations. In particular, we consider varieties that are the union of a directed family of principal +-varieties, and pseudo-principal +-varieties, that are defined in this work. Next, we consider the accuracy of the considered approximations, measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i,j-definite, k-testable and commutative approximations. Finally, we examine rough approximations under some infinite index indiscernibility relations as they were presented by Paun, Polkowski and Skowron (1997), looking at how they fit in our framework. We study their general features, comparing them with some of the families already studied, and in some cases introducing modifications in their definitions to make them congruences. Although we consider mostly Eilenberg’s +-varieties, the general ideas apply also to other types of varieties of languages. Our work may also be viewed as an approach to the characterizable inference problem in which a language of a certain kind is to be inferred from a given sample.
eng
dc.format.extent
82 p.
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Universitat Rovira i Virgili
dc.rights.license
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
inferència de llenguatges
dc.subject
varietats de llenguatges
dc.subject
conjunts aproximats
dc.subject
variedades de lenguages
dc.subject
conjuntos aproximados
dc.subject
inference of languages
dc.subject
varieties of languages
dc.subject
rough set theory
dc.subject.other
Ciències
dc.title
Rough approximations in varieties of regular languages
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
cat
dc.subject.udc
51
cat
dc.subject.udc
81
cat
dc.contributor.director
Steinby, Magnus
dc.contributor.director
Jiménez López, María Dolores
dc.embargo.terms
cap
dc.rights.accessLevel
info:eu-repo/semantics/openAccess


Documentos

TESI.pdf

2.211Mb PDF

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