Especificación algebraica de tipos abstractos de datos no deterministas

  1. Valenciano Llovera, Federico
Dirigida por:
  1. Fernando Orejas Valdés Director/a

Universidad de defensa: Universidad del País Vasco - Euskal Herriko Unibertsitatea

Año de defensa: 1988

Tribunal:
  1. Antonio Vaquero Sánchez Presidente
  2. José Ramón Garitagoitia Padrones Secretario/a
  3. Mario Rodríguez Artalejo Vocal
  4. José Luis Balcázar Navarro Vocal
  5. Ricardo Peña Marí Vocal

Tipo: Tesis

Teseo: 19621 DIALNET

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.