On the Representation of Semigroups and Other Congruences in the Lambda Calculus
| Autor: | Richard Statman |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Simply typed lambda calculus
General Computer Science representation 010102 general mathematics Syntactic monoid lambda calculus 0102 computer and information sciences 01 natural sciences semigroups Theoretical Computer Science Combinatorics 010201 computation theory & mathematics Mathematics::Category Theory Free monoid Church encoding Bicyclic semigroup Rewriting 0101 mathematics Typed lambda calculus Computer Science::Databases Trace theory Mathematics Computer Science(all) |
| Zdroj: | MFPS |
| ISSN: | 1571-0661 |
| DOI: | 10.1016/j.entcs.2016.09.044 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect