Minimal Models and Expressiveness Hierarchy

• Francicleber M. Ferreira UFC
• Ana Teresa Martins UFC

Resumo

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.

Referências

Beth, E. W. (1953). On Padoa’s method in the theory of definitions. Indag. Math., 15.

Dawar, A. and Gurevich, Y. (2002). Fixed-point logics. Bull. Symb. Logic, 8(1):65–88.

Ebbinghaus, H.-D., Flum, J., and Thomas, W. (1994). Mathematical Logic. Springer-Verlag, New York, NY.

Ferreira, F. M. (2007). Modelos Minimais e Hierarquia de Expressividade. Master’s thesis, Universidade Federal do Ceará. URL: www.lia.ufc.br/∼fran/TeseFerreira.pdf.

Ferreira, F. M. and Martins, A. T. (2006). The Predicate-Minimizing Logic MIN. In Sichman, J. S., editor, Lecture Notes in Artificial Intelligence: Proceedings of IB-ERAMIA/SBIA 2006, volume 4140, pages 581–591. Springer-Verlag, Berlin.

Ferreira, F. M. and Martins, A. T. (2007). On Minimal Models. Logic Journal of the IGPL, 15(5-6):503–526.

Lifschitz, V. (1994). Circumscription. In Gabbay, D. M., Hogger, C. J., and Robinson, J. A., editors, Handbook of Logic in Artificial Intelligence and Logic Programming-Nonmonotonic Reasoning and Uncertain Reasoning(Volume 3), pages 297–352. Clarendon Press, Oxford.

Lifschitz, V. (1995). Nested abnormality theories. Artif. Intell., 74(2):351–365.

Lloyd, J. W. (1987). Foundations of Logic Programming, 2nd Edition. Springer.

McCarthy, J. (1986). Applications of circumscription to formalizing common-sense knowledge. Artif. Intell., 28(1).

Padoa, A. (1900). Essai d’une théorie algébrique des nombres entiers, precedé d’une introduction logique a une théorie deductive qelconque. In Bibliothèque Du Congrès Int. de Philos., volume 3, pages 118–123.

Schmidt, D. A. (1986). Denotational Semantics. Allyn and Bacon, Massachusetts.

Scott, D. S. (1982). Domains for denotational semantics. In Proc. 9th Colloquium on Automata, Languages and Programming, pages 577–613, London, UK. Springer-Verlag.

van Benthem, J. (2005). Minimal predicates, fixed-points, and definability. J. Symbolic Logic, 70(3):696–712.