El objetivo central de la tesis es el estudio de los sistemas de inserción y borrado y su
capacidad computacional. Más concretamente, estudiamos algunos modelos de
generación de lenguaje que usan operaciones de reescritura de dos cadenas. También
consideramos una variante distribuida de los sistemas de inserción y borrado en el
sentido de que las reglas se separan entre un número finito de nodos de un grafo.
Estos sistemas se denominan sistemas controlados mediante grafo, y aparecen en
muchas áreas de la Informática, jugando un papel muy importante en los lenguajes
formales, la lingüística y la bio-informática. Estudiamos la decidibilidad/
universalidad de nuestros modelos mediante la variación de los parámetros de tamaño
del vector. Concretamente, damos respuesta a la cuestión más importante
concerniente a la expresividad de la capacidad computacional: si nuestro modelo es
equivalente a una máquina de Turing o no. Abordamos sistemáticamente las
cuestiones sobre los tamaños mínimos de los sistemas con y sin control de grafo. / The central object of the thesis are insertion-deletion systems and their computational
power. More specifically, we study language generating models that use two string
rewriting operations: contextual insertion and contextual deletion, and their
extensions. We also consider a distributed variant of insertion-deletion systems in the
sense that rules are separated among a finite number of nodes of a graph. Such
systems are refereed as graph-controlled systems. These systems appear in many
areas of Computer Science and they play an important role in formal languages,
linguistics, and bio-informatics. We vary the parameters of the vector of size of
insertion-deletion systems and we study decidability/universality of obtained models.
More precisely, we answer the most important questions regarding the expressiveness
of the computational model: whether our model is Turing equivalent or not. We
systematically approach the questions about the minimal sizes of the insertiondeletion
systems with and without the graph-control.
| Identifer | oai:union.ndltd.org:TDX_URV/oai:www.tdx.cat:10803/38879 |
| Date | 02 September 2011 |
| Creators | Krassovitskiy, Alexander |
| Contributors | Verlan, Serghei, Rogojin, Iurie, Bel Enguix, Gemma, Universitat Rovira i Virgili. Departament d'Antropologia, Filosofia i Treball Social |
| Publisher | Universitat Rovira i Virgili |
| Source Sets | Universitat Rovira i Virgili |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/doctoralThesis, info:eu-repo/semantics/publishedVersion |
| Format | 131 p., application/pdf |
| Source | TDX (Tesis Doctorals en Xarxa) |
| Rights | info:eu-repo/semantics/openAccess, Advertiment: La consulta d'aquesta tesi queda condicionada a l'acceptació de les següents condicions d'ús. La difusió d’aquesta tesi per mitjà del servei TDX ha estat autoritzada pels titulars dels drets de propietat intel.lectual únicament per a usos privats emmarcats en activitats d'investigació i docència. No s'autoritza la seva reproducció amb finalitats de lucre ni la seva difusió i posada a disposició des d'un lloc aliè al servei TDX. No s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant al resum de presentació de la tesi com als seus continguts. En la utilització o cita de parts de la tesi és obligat indicar el nom de la persona autora. |
Page generated in 0.0017 seconds