Article ID Journal Published Year Pages File Type
4950067 Electronic Notes in Theoretical Computer Science 2016 6 Pages PDF
Abstract
We show that every semigroup with an RE word problem can be pointwise represented in the lambda calculus. In addition, we show that the free monoid generated by an arbitrary RE subset of combinators can be represented as the monoid of all terms which fix a finite set of points.
Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Preview
On the Representation of Semigroups and Other Congruences in the Lambda Calculus
Authors
,