Tesis doctoral de Alexander Krassovitskiy
Sistemas de inserción y borrado: complejidad y capacidad de modelado 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.
Datos académicos de la tesis doctoral «Complexity and modeling power of insertion-deletion systems«
- Título de la tesis: Complexity and modeling power of insertion-deletion systems
- Autor: Alexander Krassovitskiy
- Universidad: Rovira i virgili
- Fecha de lectura de la tesis: 02/09/2011
Dirección y tribunal
- Director de la tesis
- Yurii Rogozhin
- Tribunal
- Presidente del tribunal: Carlos Martín vide
- elvira Mayordomo camara (vocal)
- giovanni Pighizzini (vocal)
- pál Dí¶mí¶si (vocal)