Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: combinatory logic

Sortuj według:

Ogranicz wyniki do:

On the complexity of the standard translation of lambda calculus into combinatory logic

Lachowski Ł.

Reports on Mathematical Logic

2018

Vol. 53

19--42

We investigate the complexity of the standard translation of lambda calculus into combinatory logic. The main result shows that the asymptotic growth rate of the size of a translated term is Θ(n3) in worst-case, where n denotes the size of the lambda term.

Programming Self-Assembly of DNA Tiles

Bellia M., Occhiuto M. E.

Fundamenta Informaticae

2016

Vol. 143, nr 1/2

35--49

The paper considers molecular programming in the abstract Tile Assembly Model, aTAM. Using simple constructions, an interpreter for the full Combinatory Logic, CL, is formally defined in aTAM. It provides an approach for sequential programming in aTAM, and produces a DNA molecular machine. This machine lives in a suitable solution and when receives a seed that linearly encodes a CL program and an input for the program, produces a grid which encodes a computation of the program on its input. The paper considers the construction cost and some alternative approaches. Finally, as a case study in distributed programming in aTAM, the paper considers the consensus problem and shows how an aTAM program for it can be formally derived by using π-calculus.

DNA Tiles, Wang Tiles and Combinators

Bellia M., Occhiuto M. E.

Fundamenta Informaticae

2014

Vol. 133, nr 2/3

105--121

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.

Solution to the Range Problem for Combinatory Logic

Intrigila B., Statman R.

Fundamenta Informaticae

2011

Vol. 111, nr 2

203-222

The lambda-theory H is obtained from beta-conversion by identifying all closed unsolvable terms (or, equivalently, termswithout head normal form). The range problemfor the theoryHasks whether a closed term has always (up to equality in H) either an infinite range or a singleton range (that is, it is a constant function). Here we give a solution to a natural version of this problem, giving a positive answer for the theory H restricted to Combinatory Logic. The method of proof applies also to the Lazy lambda-Calculus.