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

Título: Normalização de termos no cáculo dos combinadores
Autor: Teixeira, Renata Maria Machado
Orientador: Ferreira, Fernando Jorge Inocêncio
Palavras-chave: Álgebra
Lógica
Teses de mestrado
Issue Date: 2007
Resumo: 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.
Descrição: 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

Please give feedback about this item
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
Promotores do RCAAP   Financiadores do RCAAP

Fundação para a Ciência e a Tecnologia Universidade do Minho   Governo Português Ministério da Educação e Ciência PO Sociedade do Conhecimento (POSC) Portal oficial da União Europeia