Semantics for dual and symmetric combinatory calculi (Q1826434)

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.