Program of NWC 2011


(click on a presentation title to show its abstract)

Local proceedings

You can now download the full NWC 2011 booklet (local proceedings).

Monday May 23rd

09:30 Registration and coffee
10:10 Opening
Jérôme Durand-Lose
10:15 Sama GoliaeiTarbiat Modares University, Teheran (Iran)
An optical approach to computation
hide

Short abstract

Optical computing is shown to have great abilities to deal with hard computational problems, using special physical properties of light. We have provided an optical method to solve NP-complete problems in a more efficient manner than conventional computers. We have applied the method on two famous problems 3-SAT and graph 3-colorability to obtain polynomial time solutions.
download full abstract | download slides
11:00 Simon PerdrixLIG, Grenoble (France)
Beyond determinism in measurement-based quantum computation
hide download full abstract | download slides
11:45 Françoise ChatelinCERFACS, University of Toulouse 1 (France)
The legacy of Fourier, Poincaré and Einstein about relative computation
hide

Short abstract

We show how the seminal ideas of Fourier, Poincare and Einstein blend together harmoniously to explain many features of computation in Nature and in the human mind.
The Fourier analysis of complex signals leads to the Fourier transform whose complex spectum lies on the unit circle, with 4 isolated eigenvalues +1, -1, i, -i which are the 4 units of the Gaussian ring of complex integers. The Poincare approach to relativity bears on the Lorentz transformations in the algebra H of quaternions, using a noncommutative . Relative significant computation evolves from H to G2, where G is the algebra of octonions. The Einstein perspective on relativity is based on a noncommutative +, yielding a geometric 2-fold information potential with 2 types of geodesics. The potential lies in a R3 framed-metric cloth, a non-euclidean space which is a computational construct exhibiting some features attributed to either hyperbolic or elliptic aximatically defined geometries.
By mixing these 3 views with the quadratic logistic iteration, we are able to propose an algorithmic mechanism which can serve as a working model for the law of causality in Nature and mind.
download full abstract | download slides
12:30 Photo
12:35 Lunch break
14:15
Seminar
Apostolos SyropoulosGreek Molecular Computing Group, Xanthi (Greece)
Computing under vagueness
hide

Short abstract

After introducing the notion vagueness, I will talk about the various expressions of vagueness with emphasis on fuzzy set theory. In particular, I will introduce the basic set operations and I will briefly discuss the relationship of fuzzy set theory to probability theory. Next, I will discuss Zadeh's early ideas on fuzzy algorithms and fuzzy Turing machines. Then, I will formally introduce fuzzy Turing machines and fuzzy P systems. Also, I will talk about the notion of process similarity, fuzzy labeled transition systems, and finally the fuzzy chemical abstract machine.
download full abstract | download slides
15:30 Mike StannettUniversity of Sheffield (UK)
Recent discussions in cosmological computation
hide

Short abstract

Andréka, Németi and their colleagues have developed a series of first order relativity theories, in which they consider the extent to which results from relativistic physics can be derived formally from various sets of basic axioms; some of the associated models are thought to permit systems that can solve formally undecidable problems by exploiting black hole geometries. In related work, we have recently started joint work looking at the occurrence of closed timelike curves (CTCs) in general relativistic models, as might exist for example as a consequence of traversable wormholes. In this talk I will discuss some of the consequences of CTCs, and their relevance to physical computation.
download full abstract | download slides
16:15 Yaroslav D. SergeyevDEIS, University of Calabria (Italy)
Relativity in mathematical descriptions of automatic computations
hide download full abstract | download published paper
17:00 Coffee break
17:15 Hugo FéréeENS Lyon (France)
Polynomial interpretation of stream programs
hide download full abstract | download slides
17:45 Maurice MargensternLITA, Paul Verlaine University, Metz (France)
About a message system for the tiles of the heptagrid of the hyperbolic plane
hide

Short abstract

In those papers, the author considered the possiblity for cells of a cellular automaton in the pentagrid or in the heptagrid of the hyperbolic plane to communicate. In this talk, we shall present a refinment of the protocol described in these papers and we shall present a small experiment performed in order to test several assumptions about a possible ‘realization’ of this message system.
download full abstract
18:30 Discussions
20:00 Banquet at the « Brin de Zinc » restaurant (price around 20‒25€)

Tuesday May 24th

09:00 Grégory LafitteLIF, Marseille (France)
A general framework for computability
09:45 René DoursatISC-PIF and CREA Lab, École Polytechnique, Paris (France)
Toward morphogenetic engineering: biological development as a new model of programmed self-organization
hide download full abstract | download slides
10:30 Jean-Louis GiavittoIRCAM, Paris (France)
MGS: a declarative spatial computing programming language
hide

Short abstract

MGS extends the notion of rewriting by considering more general structures than terms. This extension unifies, from the programming point of view, unconventional models of computation like cellular automata, membrane computing or Lindenmayer systems. This unification relies on spatial notions: computations are structured following an underlying space representing a data structure or constraints that must be fulfilled by the computation.
In this talk, we will expose the rational of the MGS design and give some examples of MGS programs in algorithmics and in system biology.
download full abstract | download slides
11:00 Coffee break
11:15 Amaury PoulyENS Lyon (France)
Solving analytic differential equations in polynomial time over unbounded domains
hide

Short abstract

We consider the computational complexity of solving initial-value problems defined with analytic ordinary differential equations (ODEs) over unbounded domains. We show that the solution can be computed in polynomial time over its maximal interval of definition, provided it satisfies a very generous bound on its growth, and that the function admits an analytic extension over the complex numbers.
download full abstract | download slides
11:45 Jonas LefèvreLIX, École Polytechnique, Paris (France)
Equivalence between population protocols and Turing machines
hide download full abstract | download slides
12:15 Lunch break
14:00 Maxime SenotLIFO, University of Orléans (France)
A generic and modular signal machine solving satisfiability problems
hide

Short abstract

Signal machines are an abstract and geometrical model of computation, where computations consist in colored segment lines and their intersections in the Euclidean plane.
In this talk, we first introduce the model and give some basic properties, and then we illustrate the power of signal machines by a geometrical construction solving Q-SAT in bounded space and time, by the use of space-time continuity. We will also discuss some new complexities measure, more adapted to signal machines.
download full abstract | download slides
14:45 Luidnel MaignanINRIA Saclay Île-de-France (France)
Points, distances, and cellular automata: geometric and spatial algorithmics
hide

Short abstract

Spatial computing aims at providing a scalable framework where computation is distributed on a uniform computing medium and communication happen locally between nearest neighbors. We study the particular framework of cellular automata, using a regular grid and synchronous update. As a first step towards generic computation, we propose to develop primitives allowing to structure the medium around a set of particles. We consider three problems of geometrical nature: moving the particles on the grid in order to uniformize the density, constructing their convex hull, constructing a connected proximity graph establishing connection between nearest particles. The last two problems are considered for multidimensional grid while uniformization is solved specifically for the one dimensional grid.
The work approach is to consider the metric space underlying the cellular automata topology and construct generic mathematical object based solely on this metric. As a result, the algorithms derived from the properties of those objects, generalize over arbitrary regular grid. We implemented the usual ones, including hexagonal, 4 neighbors, and 8 neighbors square grid.
All the solutions are based on the same basic component: the distance field, which associates to each site of the space its distance to the nearest particle. While the distance values are not bounded, it is shown that the difference between the values of neighboring sites is bounded, enabling encoding of the gradient into a finite state field. Our algorithms are expressed in terms of movements according to such gradient, and also detecting patterns in the gradient, and can thus be encoded in finite state automata, using only a dozen of state.
download full abstract | download slides
15:30 Louis BigoLACL, University of Paris-Est Créteil (France)
Two representations of music computed with a spatial programming language
hide download full abstract | download slides
16:00 Closing
Jérôme Durand-Lose