Especificación algebraica de tipos abstractos de datos no deterministas

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

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

Any de defensa: 1988

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

Tipus: Tesi

Teseo: 19621 DIALNET

Resum

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.