Publicidad

Publicidad

becas.universia.netBiblioteca.Net

Buscar recursos:

Buscador Google

Resource data



Ver
Marcadores Sociales

The Church-Rosser property in symmetric combinatory logic
Bimbó, Katalin
Location: http://projecteuclid.org/euclid.jsl/1120224727
J. Symbolic Logic 70, iss. 2 (2005), 536-556
doi:10.2178/jsl/1120224727

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric ?-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.

Belongs to: Project Euclid (Hosted at Cornell University Library)

Publicidad

Descargar SCORM

Este recurso ha sido solicitado 1 veces (1 veces en los últimos 30 días).

Para poder solicitar este recurso debe identificarse como usuario de la biblioteca

Users rating

No hay ninguna valoración para este recurso. Sea el primero en valorar este recurso.

Detalles del recurso

The Church-Rosser property in symmetric combinatory logic
Id. 1445170
Idioma inglés
Titulo The Church-Rosser property in symmetric combinatory logic
Autor(es) Bimbó, Katalin
Location http://projecteuclid.org/euclid.jsl/1120224727
J. Symbolic Logic 70, iss. 2 (2005), 536-556
doi:10.2178/jsl/1120224727
Versión 1.0
Estado Final
Descripción Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric ?-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property.
Tipo application/pdf
Palabras clave symmetric combinatory logic
Tipo de recurso Text
Tipo de Interactividad Expositivo
Nivel de Interactividad muy bajo
Audiencia Estudiante
Profesor
Autor
Estructura Atomic
Coste no
Copyright
Copyright 2005 Association for Symbolic Logic
Formatos application/pdf
Requerimientos técnicos Browser: Any
Fecha de contribución 19-sep-2008
Contacto