Semantics for dual and symmetric combinatory calculi (Q1826434)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Semantics for dual and symmetric combinatory calculi |
scientific article |
Statements
Semantics for dual and symmetric combinatory calculi (English)
0 references
6 August 2004
0 references
A combinator is an operator which permutes, cancels or duplicates terms that follow it. For example \(((Sx)y)z\) reduces to \((xz)(yz)\). Dual combinators apply, in a similar way, to terms that precede it. For example \(x(y(zs))\) reduces to \((xy)(xz)\). Earlier papers by the author have considered syntactic properties of a system with both combinators and dual combinators and their rules and one where each combinator is identified with its dual (i.e. \(s=S\)), and variants of these with the \(\eta\) rule. These systems can be inequational, with \(\leq\) for ``reduces to'' and equational with = for ``reduces to''. The systems are shown to have algebraic semantics (posets and algebras), Routley-Meter-style relational semantics as well as operational semantics.
0 references
combinators
0 references
dual combinators
0 references
algebraic semantics
0 references
combinatory logic
0 references
equational logic
0 references
inequational logic
0 references
Kripke semantics
0 references
\(\lambda\)-calculus
0 references
operational semantics
0 references