Bibliographic Details
| Title: |
DNA Tiles, Wang Tiles and Combinators. |
| Authors: |
Bellia, Marco1 bellia@di.unipi.it, Occhiuto, M. Eugenia1 occhiuto@di.unipi.it |
| Source: |
Fundamenta Informaticae. 2014, Vol. 133 Issue 2-3, p105-121. 17p. |
| Subjects: |
Combinatory logic, Combinatorics, Programming languages, Set theory, Nonclassical mathematical logic |
| Abstract: |
We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI#, which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI# in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI#, provides a finite set of Tiles that self-assemble to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function. [ABSTRACT FROM AUTHOR] |
|
Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| Database: |
Engineering Source |
