Universidade de Lisboa Repositório da Universidade de Lisboa

Repositório da Universidade de Lisboa >
Faculdade de Ciências (FC) >
FC - Dissertações de Mestrado >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10451/1257

Title: Normalização de termos no cáculo dos combinadores
Authors: Teixeira, Renata Maria Machado
Advisor: Ferreira, Fernando Jorge Inocêncio
Keywords: Álgebra
Lógica
Teses de mestrado
Issue Date: 2007
Abstract: Neste trabalho apresenta-se um estudo clássico do Cálculo dos Combinadores Não Tipado e Tipado e aborda-se ainda o Cálculo T de Gödel como uma extensão do Cálculo dos Combinadores Tipado. No Cálculo dos Combinadores Não Tipado prova-se que é válido o Teorema de Church-Rosser e que existem alguns resultados não decidíveis, como saber se um termo admite ou não forma normal. Para o Cálculo dos Combinadores Tipado mostra-se que também é válido o Teorema de Church-Rosser e que esta teoria satisfaz o Teorema da Normalização Forte. Prova-se que estes dois últimos Teoremas também são satisfeitos pelo Cálculo T de Gödel.
This thesis presents a classical study of the Untyped and Typed Combinatory Calculus; furthermore, it studies Gödel's T Calculus as an extension of the Typed Combinatory Calculus. Regarding the Untyped Combinatory Calculus, this work proves that the Church- Rosser Theorem is valid and some undecidability results (e.g., it is undecidable whether a term admits a normal form). As far as the Typed Combinatory Calculus is concerned, not only the Church- Rosser Theorem is valid but it also enjoys the propriety of Strong Normalization. This is also the case for Gödel's T Calculus. Herein, we prove these Theorems.
Description: Tese de mestrado em Matemática (Álgebra, Lógica e Fundamentos), apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2008
URI: http://catalogo.ul.pt/F/?func=item-global&doc_library=ULB01&type=03&doc_number=000561458
http://hdl.handle.net/10451/1257
Appears in Collections:FC - Dissertações de Mestrado

Files in This Item:

File Description SizeFormat
19050_ULFC091294_TM__Renata_Teixeira.pdf1.02 MBAdobe PDFView/Open
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

 

  © Universidade de Lisboa / SIBUL
Alameda da Universidade | Cidade Universitária | 1649-004 Lisboa | Portugal
Tel. +351 217967624 | Fax +351 217933624 | repositorio@reitoria.ul.pt - Feedback - Statistics
DeGóis
  Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE