Wyniki wyszukiwania - BazTech

1

Programming Self-Assembly of DNA Tiles

Bellia M., Occhiuto M. E.

Fundamenta Informaticae

|

2016

|

Vol. 143, nr 1/2

35--49

EN

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.

2

DNA Tiles, Wang Tiles and Combinators

Bellia M., Occhiuto M. E.

Fundamenta Informaticae

|

2014

|

Vol. 133, nr 2/3

105--121

EN

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.

3

Java SAM Typed Closures : A Sound and Complete Type Inference System for Nominal Types

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2013

|

Vol. 128, nr 1-2

17--33

EN

The last proposal for Java closures, as emerged in JSR 000335, is mainly innovative in: (1) Use of nominal types, SAM types, for closures; (2) Introduction of target types and compatibility for a contextual typing of closures; (3) Need for a type inference that reconstructs the omitted type annotations of closures and closure arguments. The paper provides a sound and complete type system, with nominal types, for such a type inference and discusses role and formalization of targeting and of compatibility in the designed inference process.

4

The Equivalence of Reduction and Translation Semantics of Java Simple Closures

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2012

|

Vol. 119, nr 3/4

249-265

EN

FGCJ is a minimal core calculus that extends Featherweight Generic Java, FGJ, with lambda expressions for Java Simple Closures. It has been introduced to study, in a reduction semantics framework, properties of Java Simple Closures, including type safety and abstraction property. F is a source-to-source, translation rule system from Java 1.5 extended with lambda expressions, back to ordinary Java 1.5. It has been introduced to study, in a translation semantics framework, the design and the implementation features of lambda expressions, including simple closures, this transparency, not local variables and relations with anonymous class objects. In this paper we prove that the reduction semantics and the translation semantics commute in FGACJ. Where FGACJ is a minimal core calculus that extends FGCJ, by adding Java interfaces and anonymous class objects and that allows a restricted definition of translation semantics F.

5

Properties of Java Simple Closures

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2011

|

Vol. 109, nr 3

237-253

EN

In the last years, the Java community has been arguing about adding closures to Java in order to improve expressivity. The debate has not yet terminated but all proposals seem to converge towards a notion of Simple Closures which contain only the essential features of anonymous functions. This paper addresses the problem of defining a rigorous semantics for Simple Closures. The technique adopted is well known and has already been used to prove interesting properties of other extensions of Java. A minimal calculus is defined: Featherweight Java extended with Simple Closures. Syntax and semantics of such a calculus are defined and type safety, backward compatibility, and the abstraction property are proved.

6

JavaΩ: The Structures and the Implementation of a Preprocessor for Java with m_and mc_ parameters

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2009

|

Vol. 93, nr 1-3

45-64

EN

M_parameters extend Java by allowing methods to have methods as parameters. [8] furnishes a semantics of m parameters and applications in OO programming. In this paper, we present an implementation of the extended language based on program preprocessing. We also discuss the integration of the extended programs with ordinary Java programs, and hence Java API. Furthermore, mc_parameters are defined: they are a variant of m parameters for which the class hierarchy of the method passed as parameter must be provided in the formal and actual parameter. Semantics for mc_parameters is given but, in this case, an implementation with callbacks [20] is proposed. Eventually, we discuss how mc parameters deal with overloaded methods.

7

Methods as Parameters: A Preprocessing Approach to Higher Order in Java

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2008

|

Vol. 85, nr 1-4

35-50

EN

The paper investigates the use of preprocessing in adding higher order functionalities to Java, that is in passing methods to other methods. The approach is based on a mechanism which offers a restricted, disciplined, form of abstraction that is suitable to the integration of high order and object oriented programming. We show how this integration can be exploited in programming through the development of an example. Then, we discuss how the expressive power of the language is improved. A new syntax is introduced for formal and actual parameters, hence the paper defines a translation that, at preprocessing time, maps programs of the extended language into programs of ordinary Java.

8

Higher order Programming in Java : Introspection, Subsumption and Extraction

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2005

|

Vol. 67, nr 1-3

29--44

EN

Higher order programming is considered a good methodology for program design and specification, furthermore it is fundamental for rapid prototyping. The paper is devoted to higher order programming in Java and, more in general, in the OO programming paradigm. We discuss introspection to write higher order programs and compare this technique with other different, interesting approaches, including function emulation and function integration. Finally, we address the problem of embedding, in the OO paradigm, the mechanisms for method passing and method extraction that are basic to the higher order programming methodology.

9

N-axioms Parallel Unification

Bellia M., Occhiuto M.E.

Fundamenta Informaticae

|

2003

|

Vol. 55, nr 2

115-128

EN

MGUmon and MGUk-rep have a complementary role in unification in the complexity class NC . MGUmon is the upper bound of the unification classes that fall in NC and whose inputs admit an unrestricted number of repeated variables. MGUk-rep is the upper bound of the unification classes that still fall in NC but whose inputs admit an unrestricted arity on term constructors. No LogSpace reduction of the one to the other class is known. Moreover, very fast algorithms that solve the two separately are well known but no one is able to compute with both in polylog PRAM-Time. N-axioms unification extends the structure of unification inputs and brings out the notion of interleaving variable as a special repeated variable which serializes independet computations. Based on it, we define the unification class AMGUkp/h whose inputs have a fixed number of interleaving variables but admit unrestricted number of repeated variables and, at the same time, unrestricted arity for term constructors. Constructively, we prove that AMGUkp/h is in NC by introducing a new unification algorithm that works on graph contractions and solves AMGUkp/hin a polylog PRAM time of the input size. Finally, we prove that MGUmon, MGUk-rep and MGUlinear all are LogSpace reducible to AMGUkp/h. Hence, AMGUkp/h becomes the upper bound of the unification classes that are proved to be in NC .