Francicleber Martins Ferreira,  Ana 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.

http://www.springerlink.com/content/cn682857l6q5241t

Processando consulta.