DNA Tiles, Wang Tiles and Combinators.
Saved in:
| 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 98579479 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: DNA Tiles, Wang Tiles and Combinators. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Bellia%2C+Marco%22">Bellia, Marco</searchLink><relatesTo>1</relatesTo><i> bellia@di.unipi.it</i><br /><searchLink fieldCode="AR" term="%22Occhiuto%2C+M%2E+Eugenia%22">Occhiuto, M. Eugenia</searchLink><relatesTo>1</relatesTo><i> occhiuto@di.unipi.it</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Fundamenta+Informaticae%22">Fundamenta Informaticae</searchLink>. 2014, Vol. 133 Issue 2-3, p105-121. 17p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Combinatory+logic%22">Combinatory logic</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorics%22">Combinatorics</searchLink><br /><searchLink fieldCode="DE" term="%22Programming+languages%22">Programming languages</searchLink><br /><searchLink fieldCode="DE" term="%22Set+theory%22">Set theory</searchLink><br /><searchLink fieldCode="DE" term="%22Nonclassical+mathematical+logic%22">Nonclassical mathematical logic</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=98579479 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.3233/FI-2014-1065 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 17 StartPage: 105 Subjects: – SubjectFull: Combinatory logic Type: general – SubjectFull: Combinatorics Type: general – SubjectFull: Programming languages Type: general – SubjectFull: Set theory Type: general – SubjectFull: Nonclassical mathematical logic Type: general Titles: – TitleFull: DNA Tiles, Wang Tiles and Combinators. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Bellia, Marco – PersonEntity: Name: NameFull: Occhiuto, M. Eugenia IsPartOfRelationships: – BibEntity: Dates: – D: 10 M: 06 Text: 2014 Type: published Y: 2014 Identifiers: – Type: issn-print Value: 01692968 Numbering: – Type: volume Value: 133 – Type: issue Value: 2-3 Titles: – TitleFull: Fundamenta Informaticae Type: main |
| ResultId | 1 |
