The Predicate-Minimizing Logic MIN

Francicleber Martins FerreiraAna Teresa C. Martins

The concept of minimization is widely used in several areas of Computer Science. Although this notion is not properly formalized in first-order logic, it is so with the logic MIN(FO) [13] where a minimal predicate P is defined as satisfying a given first-order description @(P). We propose the MIN logic as a generalization of MIN(FO) since the extent of a minimal predicate P is not necessarily unique in MIN as it is in MIN(FO). We will explore two different possibilities of extending MIN(FO) by creating a new predicate defined as the union, the U-MIN logic, or intersection, the I-MIN logic, of the extent of all minimal P that satisfies @(P). We will show that U-MIN and I-MIN are interdefinable. Thereafter, U-MIN will be just MIN. Finally, we will prove that simultaneous minimizations does not increase the expressiveness of MIN, and that MIN and second-order logic are equivalent in expressive power.

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato:
     Mantida por: