1992 research reports / rapport de recherche 1992

Cellular Encoding of Genetic Neural Networks.

• By: Frederic Gruau
• Number: RR1992-21
• Date: April 92
• Abstract:

  It is now recognized that the key point in successful application of Genetic Algorithms GA to an optimization problem, is the scheme used to encode solutions on the structure manipulated by the GA. Despite the fundamental importance of the encoding, there has not yet been any attempt to establish a description of which theoretical properties this encoding should have in the particular case of neural network optimization. This paper is divided in two part. In the first part, seven theoretical and verifiable properties that rate an encoding of neural networks are defined. The properties are:completeness, compactness, closure, modularity, scalability, power of expression, abstraction. An encoding called ``Cellular Encoding'' with all these properties is described. It is an extension of an encoding scheme that has already given surprising experimental results. The analysis of the seven properties gives a theoretical explanation for its empirical success. In the second part, continuing the presentation of the Cellular Encoding of neural networks, the alphabet of the code is extended so as to form a neural network machine language. A compiler for this machine language is described. It compiles programs written with a subset of the language PASCAL. This fact allows to complete the properties of Cellular Encoding.

• Keywords:

  Neural Networks, Genetic Algorithms, Encoding, Compilation.

• Availability: Electronic copy only.
• Citation: To appear in Theoretical computer science, Maurice Nivat ed, Elsevier, 1995 (only the second part of the report).
• Size: 3+41p
• Format: Compressed PostScript
• Get it

A hypercube algorithm for connected component labeling of volumic images.

• By: Laurent Perroton
• Number: RR1992-39
• Date: July 1992
• Abstract:

  The purpose of this article is to present a parallel implementation of a component labeling algorithm, taking advantages of hypercube interconnection capabilities. Our parallel implementation can be adapted to the processing of two dimensional as well as three dimensional images. We partition the data on a linear network, and apply the classical sequential algorithm on each subdomain. The hypercube topology is fully exploited for merging data. Our allocation strategy allows to introduce easily load balancing features. Our experiments performed on 3D biomedical images of a wrist show the efficiency of the parallelization.

• Keywords:

  Component Labeling, Volumic Imaging, Parallelism, Hypercube, iPSC860.

• Availability: Paper copy available.
• Citation: Published in ICPADS conference, Proceedings International Conference on Parallel and Distributed Systems, 1992.
• Size: 2+18p
• Format: Compressed PostScript
• Get it

The Data-Parallel Programming Model: a Semantic Perspective (Preliminary Version).

• By: Luc Bouge
• Number: RR1992-45
• Abstract:

  We propose a short introduction to the Data-Parallel programming model. We show that parallel computing often makes little distinction between the execution model and the programming model. This results in poor programming and low portability. Using the |GOTO| considered harmful seminal analogy, we show that data-parallelism can be seen as a way out of this collapsing. We show that this model was already present in several works on parallel programming methodology, and that it can be characterized by a small number of concepts with simple semantics.

• Keywords:

  Programming Languages, Data-Parallelism, Operational Semantics, Programming Models.

• Availability: Electronic copy only.
• Size: 2+12p
• Format: Compressed PostScript
• Get it

Recouvrement d'une piece trapezoidale par des dominos. Tiling a trapezoidal region with dominoes.

• By: Luc Bouge , Michel Cosnard
• Number: RR1992-46
• Date: February 1, 1992
• Abstract:

  We give two elementary proofs for the following result. Any trapezoidal region of the plane can be tiled by by h2 (2 x 1) and v2 (1 x 2) dominoes. The first one is constructive and leads to a construction method in linear time with respect to the surface. The second one leads to a non-deterministic construction method which yields any possible tiling.

• Keywords:

  Tiling Problem, Trapezoidal Region, Tiling Complexity.

• Availability: Electronic copy only.
• Citation: Published in Comptes Rendus de l'Academie des Sciences de Paris, vol. 315, series I, p. 221-226, 1992.
• Size: 2+8p
• Format: Compressed PostScript
• Get it

Control structures for data-parallel SIMD languages semantics and implementation.

• By: Luc Bouge , Jean-Luc Levaire
• Number: RR1992-47
• Date: January 8, 1992
• Abstract:

  We define a simple language which encapsulates the main concepts of SIMD data-parallel programming, and we give its operational semantics. This language includes a unique data-parallel control structure called multitype conditioning and escape. We show that it suffices to express all data-parallel extensions of usual scalar control structures of C, as found in C*, MPL, POMPC etc. Moreover, we give a formal correctness proof for two different implementations of this new statement, respectively by a single context stack, and by a set of counters. Thus, this simple language appears as an interesting basis to study data-parallel SIMD programming methodology.

• Keywords:

  Data-Parallel Programming, Operational Semantics, Program Equivalence, Multitype Condidioning, Massively Parallel Programming Methodology.

• Availability: Electronic copy only.
• Citation: Published in Future Generation Computer Systems, vol. 8, 1992, pp. 363-378.
• Size: 2+22p
• Format: Compressed PostScript
• Get it

A-translation and Looping Combinators in Pure Type Systems.

• By: Thierry Coquand , Hugo Herbelin
• Number: RR1992-48
• Date: January 7, 1993.
• Abstract:

  We present here a generalization of $A$-translation to a class of Pure Type Systems. We apply this translation to give a direct proof of the existence of a looping combinator in a large class of inconsistent type systems including type systems with a type of all types. This is the first non-automated solution to this problem.

• Keywords:

  A-Translation, Fixed-Point Combinator, Type Systems.

• Availability: Paper copy available.
• Citation: Published in Journal of Functional Programming, vol 4, pp 77-88, 1994.
• Size: 2+9p
• Format: Compressed PostScript
• Get it

Inductive Definitions in the system Coq: Rules and Properties.

• By: Christine Paulin-Mohring
• Number: RR1992-49
• Date: January 8, 1993
• Abstract:

  In the pure Calculus of Constructions, it is possible to represent data structures and predicates using higher-order quantification. However, this representation is not satisfactory, from the point of view of both the efficiency of the underlying programs and the power of the logical system. For these reasons, the calculus was extended with a primitive notion of inductive definitions. This paper describes the rules for inductive definitions in the system Coq. They are general enough to be seen as one formulation of adding inductive definitions to a typed lambda-calculus. We prove strong normalization for a subsystem of Coq corresponding to the pure Calculus of Constructions plus Inductive Definitions with only weak non-dependent eliminations.

• Keywords:

  Inductive Definitions, Typed Lambda-Calculus, Calculus of Constructions.

• Availability: Paper copy available.
• Citation: Published in Proceedings of Typed Lambda Calculus and Applications conference, Lecture Note in Computer Science, N° 664, M. Bezem & J.F. Groot eds, 1993.
• Size: 2+20p
• Format: Compressed PostScript
• Get it