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.
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 Goliaei ‒ Tarbiat 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
download full abstract | download slides
|
|
11:00 |
Simon Perdrix ‒ LIG, Grenoble (France) Beyond determinism in measurement-based quantum computation |
hide download full abstract | download slides | |
11:45 |
Françoise Chatelin ‒ CERFACS, 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.
download full abstract | download slides
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. |
|
12:30 | Photo |
12:35 | Lunch break |
14:15 Seminar |
Apostolos Syropoulos ‒ Greek 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 Stannett ‒ University 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. Sergeyev ‒ DEIS, 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ée ‒ ENS Lyon (France) Polynomial interpretation of stream programs |
hide download full abstract | download slides | |
17:45 |
Maurice Margenstern ‒ LITA, 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 Lafitte ‒ LIF, Marseille (France) A general framework for computability |
09:45 |
René Doursat ‒ ISC-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 Giavitto ‒ IRCAM, Paris (France)MGS : a declarative spatial computing programming language
|
hide
Short abstractMGS 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.
|
|
11:00 | Coffee break |
11:15 |
Amaury Pouly ‒ ENS 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èvre ‒ LIX, École Polytechnique, Paris (France) Equivalence between population protocols and Turing machines |
hide download full abstract | download slides | |
12:15 | Lunch break |
14:00 |
Maxime Senot ‒ LIFO, 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.
download full abstract | download slides
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. |
|
14:45 |
Luidnel Maignan ‒ INRIA 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.
download full abstract | download slides
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. |
|
15:30 |
Louis Bigo ‒ LACL, 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 |