Título
Simulación en tiempo constante de un modelo R-Mesh en un LR-Mesh
Constant time simulation of an R-Mesh model on an LR-Mesh model
Autor
Carlos Alberto Córdova Flores
Colaborador
JOSE ALBERTO FERNANDEZ ZEPEDA (Asesor de tesis)
Nivel de Acceso
Acceso Abierto
Materias
Resumen o descripción
Se creía que el modelo LR-Mesh era computacionalmente menos poderoso que el modelo R-Mesh. Omer Reingold mostró un algoritmo para la máquina de Turing que resuelve USTCON requiriendo O(logN) unidades de espacio, implicando que las clases de complejidad L y SL son equivalentes. Los modelos LR-Mesh y R-Mesh son capaces de resolver los problemas de las clases L y SL en tiempo constante, respectivamente. Por lo tanto, los resultados de Reingold implican que los modelos LR-Mesh y R-Mesh son computacionalmente igual de poderosos. En el presente trabajo se describe una simulación del modelo R-Mesh en el LR-Mesh en tiempo constante. La mejor simulación conocida requería de O(logN) unidades de tiempo. Se muestra cómo se puede convertir un grafo regular cualquiera en un expansor y como resolver el problema USTCON en un expansor en el modelo LR-Mesh siguiendo el algoritmo de Reingold. Con estos resultados se construye la smulación entre los modelos en tiempo constante. Finalmente se muestra un análisis de los recursos (procesadores) requeridos por dicha simulación.
There was the assumption that the LR-Mesh model was computationally less powerful than the R-Mesh. Omer Reingold showed an algorithm for the Turing machine that solves USTCON problem with O(logN) space units, implying that the complexity classes L and SL are equivalent. The LR-Mesh and R-Mesh models are capable of solving the problems that belong to the classes L and SL in constant time, respectively. Hence, Omer Reingold’s results implies that the model LR-Mesh is computationally as powerful as the R-Mesh. The present work decribes a simulation of the R-Mesh model on the LR-Mesh in constant time. The best simulation known required O(logN) time units. It shows how to transform a regular graph into an expander and how to solve USTCON in an expander graph on the LR-Mesh, following Reingold’s algorithm. With these results the constant time simulation between the models is constructed. Finally it shows an analysis of the resources (processors) required for the stated simulation.
Editor
CICESE
Fecha de publicación
2007
Tipo de publicación
Tesis de maestría
Recurso de información
Formato
application/pdf
Idioma
Español
Sugerencia de citación
Córdova Flores, C. A.2007.Simulación en tiempo constante de un modelo R-Mesh en un LR-Mesh.Tesis de Maestría en Ciencias. Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.132 pp.
Repositorio Orígen
Repositorio Institucional CICESE
Descargas
396