Propiedades estructurales de las jerarquías de conteo
- Teran Romero, Jacobo
- José Luis Balcázar Navarro Zuzendaria
Defentsa unibertsitatea: Universitat Politècnica de Catalunya (UPC)
Defentsa urtea: 1988
- Josep Díaz Cort Presidentea
- Llorenç Huguet Rotger Idazkaria
- Joaquim Gabarró Vallés Kidea
- Uwe Schoning Kidea
- Mario Rodríguez Artalejo Kidea
Mota: Tesia
Laburpena
SE ESTUDIAN TRES JERARQUIAS RELACIONADAS CON LA NOCION DE CONTAR: LA JERARQUIA DE CONTEO DE TIEMPO POLINOMICO, LA DE FUNCIONES DE CONTEO Y LA JERARQUIA DE CONTEO DE TIEMPO LOGARITMICO, INVESTIGAMOS LAS CONEXIONES ENTRE ESTAS JERARQUIAS Y ESTUDIAMOS SUS PROPIEDADES ESTRUCTURALES, OBTENIENDO RESULTADOS QUE RESUELVEN PROBLEMAS ABIERTOS RELATIVOS A CARACTERIZACION MEDIANTE ORACULOS, CIERRE POR OPERACIONES BOOLEANAS, CONJUNTOS BAJOS, REPRESENTACIONES SUCINTAS Y RELACIONES CON OTRAS CLASES DE COMPLEJIDAD.