Especificación algebraica de tipos abstractos de datos no deterministas

• Autores: Federico Valenciano Llovera
• Directores de la Tesis: Fernando Orejas Valdés (dir. tes.)
• Lectura: En la Universidad del País Vasco - Euskal Herriko Unibertsitatea ( España ) en 1988
• Idioma: español
• Tribunal Calificador de la Tesis: Antonio Vaquero Sánchez (presid.) , José Ramón Garitagoitia Padrones (secret.) , Mario Rodríguez Artalejo (voc.) , José Luis Balcázar Navarro (voc.) , Ricardo Peña Marí (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • SE PROPONE UN FORMALISMO PARA EL TRATAMIENTO DEL INDETERMINISMO EN EL CONTEXTO DE LA ESPECIFICACION ALGEBRAICA DE TIPOS DE DATOS CUYAS BASES SON LAS SIGUIENTES: 1) EL USO DE LAS ALGEBRAS ORDENADAS (CIERTA CLASE RESTRINGIDA DE ELLAS) COMO MEDIO PARA DESCRIBIR COMPORTAMIENTOS NO DETERMINISTAS; ES DECIR COMO EXPRESION FORMAL DE LA NOCION DE TIPO DE DATOS NO DETERMINISTA, 2) LA UTILIZACION DE SISTEMAS MIXTOS DE ECUACIONES E INECUACIONES CON VARIABLES DE INSTANCIACION RESTRINGIDA PARA SU ESPECIFICACION. FORMULANDOSE CONDICIONES BAJO LAS CUALES ES POSIBLE TOMAR SEMANTICA INICIAL Y FINAL EN ESTAS ESPECIFICACIONES.

    3) POSIBILIDAD DE DOTAR A LAS ESPECIFICACIONES DE UNA SEMANTICA OPERACIONAL BASADA EN REESCRITURA SI SE SATISFACEN CIERTOS REQUISITOS (TERMINACION FINITA Y CONFLUENCIA PARCIAL).

    COMPLETAN ESTOS RESULTADOS UNA EXTENSION DEL TEOREMA DE KNUTH-BENDIX QUE PERMITE DECIDIR SI ESTA CONDICION DE CONFLUENCIA PARCIAL ES SATISFECHA POR UN SISTEMA MIXTO FINITO Y TERMINANTE Y UNA ADAPTACION DEL ALGORITMO DE KNUTH-BENDIX QUE PERMITE CUANDO ACABA CON EXITO COMPLETAR SISTEMAS QUE NO SATISFAGAN ESTAS CONDICIONES.

    SE FORMULA ASI MISMO UN CONCEPTO DE IMPLEMENTACION BASADO EN LA IDEA DE REFINAMIENTO (REDUCCION DEL GRADO DE INDETERMINISMO) Y UN CONCEPTO DE IMPLEMENTACION DETERMINISTA DE ESPECIFICACIONES NO DETERMINISTAS ESTABLECIENDOSE CONDICIONES SUFICIENTES PARA SU EXISTENCIA.