Minimal Models and Expressiveness Hierarchy - Ferreira, Francicleber M.; Martins, Ana Teresa (Anais do Concurso de Teses e Dissertações da SBC (CTD-SBC), 2008)
The minimality concept is widely used in Computer Science to define objects. We find this concept in the definition of inductive sets, in denotational semantics for recursive programs, in Logic Programming, in Artificial Intelligence, etc. We analysed the minimality concept from a logical standpoint. We investigated logics whose semantics are based on minimal models, and its applications to Computer Science. Among our main results, we demonstrated theorems about definability and the expressive power of Least Fixed-Point Logic (LFP), Lifschitz’s Nested Abnormality Theories (NATs), McCarthy’s Circumscription and the MIN extension of van Benthem’s MIN(FO) Logic.