Page principale
Recherches

Formaté avec bibtex2html

Publications de Jérôme Durand-Lose

Thèses
(Co-)Édition d'actes
(Co-)Édition de numéros spéciaux
Chapitres de livre
Chapitres de livre en français
Revues internationales
Conférences internationales
Workshops internationaux (éventuellement sans publication)
Workshops nationaux (éventuellement sans publication)
Rapports de recherches non publiés
Médiatisation
Soumis

Thèses

[DL03]
Jérôme Durand-Lose. Calculer géométriquement sur le plan -- machines à signaux. Habilitation à Diriger des Recherches, École Doctorale STIC, Université de Nice-Sophia Antipolis, 2003. In French. [ bib | .html | .pdf ]
Ce mémoire se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations.

Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires. Le mémoire commence par une présentation des automates cellulaires et des particules. Nous faisons ensuite une classification des différents modèles de calcul existants et mettons en valeur leurs aspects discrets et continus. À notre connaissance, notre modèle est le seul à temps et espace continus mais à valeurs et mises à jour discrètes.

Dans la première partie du mémoire, nous présentons ce modèle, les machines à signaux, et montrons comment y mener tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs). Nous montrons comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné).

Dans la seconde partie du mémoire, nous cherchons à caractériser les points d'accumulation. Nous reformulons de manière topologique les diagrammes espace-temps: pour chaque position, la valeur doit correspondre au voisinage sur un ouvert suffisamment petit. Muni de cet outil, nous regardons les plus simples accumulations possibles (les singularités isolées) et proposons un critère pour y prolonger le calcul; mais le déterminisme peut être perdu dans le cône d'influence. Enfin, en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles, nous montrons que le problème de la prévision de l'apparition d'une accumulation est Σ20-complet.

Le mémoire se conclut par la présentation de nombreuses perspectives de recherches.

[DL96]
Jérôme Durand-Lose. Automates Cellulaires, Automates à Partitions et Tas de Sable. Thèse de doctorat, LaBRI, 1996. In French. [ bib | .html | .pdf ]
Cette thèse s'intéresse dans un premier temps aux automates cellulaires réversibles, et dans un second temps aux tas de sable linéaires.

Nous construisons diverses simulations reliant les automates cellulaires aux automates à partitions, en particulier celle des automates cellulaires réversibles par les automates à partitions réversibles, ce qui était une conjecture depuis 1990. Par des constructions successives, nous montrons que le “Billiard ball model” de Toffoli et Margolus est capable de simuler tous les automates à partitions réversibles de dimension 2. En rassemblant ces résultats, nous montrons qu'il existe des automates cellulaires réversibles capables de simuler tous les automates cellulaires réversibles de même dimension.

Dans un espace linéaire, “Tas de sable” et “Chip firing game” sont équivalents. Nous portons notre attention sur le cas où les grains tombent un à un. Des motifs délimités par des signaux apparaissent au sein des configurations engendrées. Nous étudions la dynamique du système et démontrons un équivalent asymptotique. Nous étendons nos méthodes et nos résultats à d'autres types de configurations initiales. Dans chaque cas étudié, le temps parallèle est inférieur au temps séquentiel dans un rapport de l'ordre du nombre de piles mises en oeuvre.

(Co-)Édition d'actes

[DLN15]
Jérôme Durand-Lose and Benedek Nagy, editors. Machines, Computations and Universality (MCU '15), number 9288 in LNCS. Springer, 2015. [ bib | DOI | http ]
[DLJ12]
Jérôme Durand-Lose and Nataša Jonoska, editors. Unconventional Computation and Natural Computation (UCNC '12), number 7445 in LNCS. Springer, 2012. [ bib | DOI | http ]
[DLM07]
Jérôme Durand-Lose and Maurice Margenstern, editors. Machines, Computations and Universality (MCU '07), number 4664 in LNCS. Springer, 2007. [ bib | DOI | http ]

(Co-)Édition de numéros spéciaux

[DLJ14]
Jérôme Durand-Lose and Nataša Jonoska. Special issue on Unconventional Computation and Natural Computation (UCNC '12). Nat Comput, 13(2):193--283, 2014. [ bib | DOI ]
[DL13]
Jérôme Durand-Lose. Special issue on New Worlds of Computation (NWC '11). Int J Unconventional Computing, 9(1--2):1--201, 2013. [ bib | .html ]
[MDLS12]
Maurice Margenstern, Jérôme Durand-Lose, and Klaus Sutner. Special issue on Frontier between decidability and undecidability and related problems. Int. J. of Foundations of Computer Science, 23(7):1419--1522, 2012. [ bib | DOI ]
[DL11]
Jérôme Durand-Lose. Special issue on New Worlds of Computation (NWC '09). Int J Unconventional Computing, 7(4):221--311, 2011. [ bib | .html ]
[MDL09]
Maurice Margenstern and Jérôme Durand-Lose. Special issue on Machines, Computations and Universality (MCU '07). Fund Inf, 91(1--2):1--195, 2009. [ bib | DOI ]
[ADL04]
Helmut Alt and Jérôme Durand-Lose. Special issue on STACS 2002. Theory of Computing Systems, 37(1):3--246, 2004. [ bib ]

Chapitres de livre

[DL16]
Jérôme Durand-Lose. Computing in Perfect Euclidean Frameworks. In Andrew Adamatzky, editor, Advances in Unconventional Computing, volume 1: Theory, pages 141--163. Springer, 2016. [ bib | DOI ]
This chapter presents what kind of computation can be carried out using an Euclidean space---as input, memory, outp ut...---with dedicated primitives. Various understandings of computing are encountered in such a setting allowing classical (Turing, discrete) computati ons as well as, for some, hyper and analog computations thanks to the continuity of space. The encountered time scales are discrete or hybrid (continuous evolution between discrete transitions).

The first half of the chapter presents three models of computation based on geometric concepts---namely: ruler and compass, local constrains and emergence of polyhedra and piece-wise constant derivative.

The other half concentrates on signal machines: line segments are extended; when they meet, they are replaced by othe rs. Not only are these machines capable of classical computation but moreover, using the continuous nature of space and t ime they can also perform hyper-computation and analog computation. It is possible to build fractals and to go one step further on to use their partial generation to solve, , quantif ied SAT in “constant space and time”.

[ADL12]
Andrew Adamatzky and Jérôme Durand-Lose. Collision computing. In David Corne, editor, Handbook of Natural Computing, Section VII: Broader Perspective --- Alternative Models of Computation, chapter 58, pages 1949--1978. Springer, 2012. [ bib | DOI | .pdf ]
Collision-based computing is an implementation of logical circuits, mathematical machines or other computing and information processing devices in homogeneous uniform unstructured media with traveling mobile localizations. A quanta of information is represented by a compact propagating pattern (glider in cellular automata, soliton in optical system, wave-fragment in excitable chemical system). Logical truth corresponds to presence of the localization, logical false to absence of the localization; logical values can be also represented by a particular state of the localization. When two more or more traveling localizations collide they change their velocity vectors and/or states. Post-collision trajectories and/or states of the localizations represent results of a logical operations implemented by the collision. One of the principle advantages of the a collision-based computing medium —hidden in 1D systems but obvious in 2D and 3D media— is that the medium is architecture-less: nothing is hardwired, there are no stationary wires or gates, a trajectory of a propagating information quanta can be see as a momentary wire. We introduce basics of collision-based computing, and overview the collision-based computing schemes in 1D and 2D cellular automata and continuous excitable media. Also we provide an overview of collision-based schemes where particles/collisions are dimensionless.

[DL09]
Jérôme Durand-Lose. Cellular automata, Universality of. In Robert A. Meyers and Andrew Adamatzky, editors, Encyclopedia of Complexity and System Science, pages 901--913. Springer, 2009. [ bib | DOI | http | .pdf ]
[DL02]
Jérôme Durand-Lose. Computing inside the billiard ball model. In Andrew Adamatzky, editor, Collision-based computing, pages 135--160. Springer, 2002. [ bib | .pdf ]

Chapitres de livre en français

[BDL15]
Florent Becker and Jérôme Durand-Lose. Construire et calculer dans un monde 2D. In Nicolas Ollinger, editor, Informatique Mathématique --- une photographie en 2015, pages 135--177. CNRS édition, 2015. [ bib | slides | .pdf ]
Ce chapitre présente ce qu’il est possible d’accomplir dans un espace euclidien en considérant justement cet espace (comme entrée, support, mémoire…). Accomplir à la fois comme calculs (au sens discret, mais aussi continu) et comme construction d’objet.

Trois modèles de calcul basés sur des primitives géométriques — l’utilisation de la règle et du compas, l’émergence de polyèdres ou l’utilisation de dérivées constantes — sont présentés.

Les machines à signaux sont ensuite définies : des segments de droite sont prolongés et, dès qu’ils se rencontrent, ils sont remplacés. Ces machines sont capables de calculer au sens classique. De part la nature continue de l’espace-temps, hyper-calcul comme calcul analogique sont également possibles. De plus, en contrôlant la génération de fractales, le calcul fractal permet de résoudre SAT quantifié en « temps et espace constant ». Finalement, les assemblages autonomes d’éléments discrets dans le plan forment un modèle d’une grande richesse. Celui-ci relie des objets théoriques et combinatoires que sont les pavages avec des réalisations possibles dans un modèle bio-informatique (calcul à ADN). Le calcul obtenu est asynchrone, et la synchronisation se fait par la géométrie. Temps et espace sont deux dimensions fortement intriquées.

Revues internationales

[BDL17]
Tom Besson and Jérôme Durand-Lose. Abstract Geometrical Computation 9: Exact Discretization of 3-speed Rational Signal machines. J Cell Autom, 12(3--4):159--187, 2017. [ bib | http ]
[DL12a]
Jérôme Durand-Lose. Abstract Geometrical Computation 6: a Reversible, Conservative and Rational Based Model for Black Hole Computation. Int J Unconventional Computing, 8(1):33--46, 2012. [ bib | .pdf ]
In the context of Abstract geometrical computation, it has been proved that black hole model (and SAD computers) can be implemented. To be more physic-like, it would be interesting that the construction is reversible and preserves some energy. There is already a (energy) conservative and reversible two-counter automaton simulation.

In the present paper, based on reversible and conservative stacks, reversible Turing machines are simulated. Then a shrinking construction that preserves these properties is presented. All together, a black hole model implementation that is reversible and conservative (both the shrinking structure and the universal Turing machine) is provided.

[DL12b]
Jérôme Durand-Lose. Abstract geometrical computation 7: Geometrical accumulations and computably enumerable real numbers. Nat Comput, 11(4):609--622, 2012. Special issue on Unconv. Comp. '11. [ bib | DOI | .pdf ]
Using rules to automatically extend a drawing on an Euclidean space might lead to accumulating drawings into a single point. Such points are characterized in the context of Abstract geometrical computation.

Colored line segments (traces of signals) are drawn according to rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. Time and space are continuous and accumulations can happen. Constructions exist to unboundedly accelerate a computation and provide, in a finite duration, exact analog values as limits/accumulations.

Starting with rational numbers for coordinates and speeds, the time of any isolated accumulation is a c.e.-R (computably enumerable) real number. There is a signal machine and an initial configuration that accumulates at any c.e.-R time. Similarly, the spatial positions of isolated accumulations are exactly the d.-c.e.-R (difference of computably enumerable) numbers. Moreover, there is a signal machine that can accumulate at any c.e.-R time or d.-c.e.-R position depending only on the initial configuration.

These existence results rely on a two-level construction: an inner structure simulates a Turing machine that output orders to the outer structure which handles the accumulation.

[DL11b]
Jérôme Durand-Lose. Abstract geometrical computation 5: embedding computable analysis. Nat Comput, 10(4):1261--1273, 2011. Special issue on Unconv. Comp. '09. [ bib | DOI | .pdf ]
Extended Signal machines are proven capable to compute any computable function in the understanding of recursive/computable analysis (CA), represented here with type-2 Turing machines (T2-TM) and signed binary. This relies on a mixed representation of any real number as an integer (in signed binary) plus an exact value in (-1,1). This permits to have only finitely many signals present simultaneously. Extracting a (signed) bit, improving the precision by one bit and iterating a T2-TM only involve standard signal machines.

For exact CA-computations, T2-TM have to deal with an infinite entry and to run through infinitely many iterations to produce an infinite output. This infinite duration can be provided by an infinite acceleration construction. Extracting/encoding an infinite sequence of bits is achieved as the limit of the approximation process with a careful handling of accumulations.

[DL11a]
Jérôme Durand-Lose. Abstract geometrical computation 4: Small Turing universal signal machines. Theoret Comp Sci, 412:57--67, 2011. [ bib | DOI | .pdf ]
This article provides several very small signal machines able to perform any computation ---in the classical understanding--- generated from Turing machines, cellular automata and cyclic tag systems. A halting universal signal machine with 13 meta-signals and 21 collision rules is presented (resp. 15 and 24 for a robust version). If infinitely many signals are allowed to be present in the initial configuration, 5 meta-signals and 7 collision rules are enough to achieve non-halting weak universality (resp. 6 and 9 for a robust version).

[DL09]
Jérôme Durand-Lose. Abstract geometrical computation 3: Black holes for classical and analog computing. Nat Comput, 8(3):455--472, 2009. [ bib | DOI | .pdf ]
[DL06]
Jérôme Durand-Lose. Abstract geometrical computation 1: Embedding black hole computations with rational numbers. Fund Inf, 74(4):491--510, 2006. [ bib | .pdf ]
[DL04]
Jérôme Durand-Lose. A Kleene theorem for piecewise constant signals automata. Inform Process Lett, 89(5):237--245, 2004. [ bib | DOI | .pdf ]
[BDLGJ02]
Joffroy Beauquier, Jérôme Durand-Lose, Maria Gradinariu, and Colette Johnen. Token-based self-stabilizing uniform algorithms. Journal of Parallel and Distributed Computing, 62(5):899--921, 2002. [ bib | DOI | .pdf ]
[DL01]
Jérôme Durand-Lose. Back to the universality of the Billiard ball model. Multiple Valued Logic, 6(5--6):423--437, 2001. [ bib | .pdf ]
[DL00a]
Jérôme Durand-Lose. Randomized uniform self-stabilizing mutual exclusion. Inform Process Lett, 74:203--207, 2000. [ bib | DOI | .pdf ]
[DL00b]
Jérôme Durand-Lose. Reversible space-time simulation of cellular automata. Theoret Comp Sci, 246(1--2):117--129, 2000. [ bib | DOI | .pdf ]
The goal of this paper is to design a reversible d-dimensional cellular automaton which is capable of simulating the behavior of any given d-dimensional cellular automaton over any given configuration (even infinite) with respect to a well suited notion of simulation we introduce. We generalize a problem which was originally addressed in a paper by Toffoli in 1977. He asked whether a d-dimensional reversible cellular automaton could simulate d-dimensional cellular automata. In the same paper he proved that there exists a d+1-dimensional reversible cellular automaton which can simulate a given d-dimensional cellular automaton. To prove our result, we use as an intermediate model partition cellular automata defined by Morita et al. in 1989.

[DL98]
Jérôme Durand-Lose. Parallel transient time of one-dimensional sand pile. Theoret Comp Sci, 205(1--2):183--193, 1998. [ bib | DOI | .pdf ]
[DL96]
Jérôme Durand-Lose. Grain sorting in the one dimensional sand pile model. Complex Systems, 10(3):195--206, 1996. [ bib | .pdf ]

Conférences internationales

[DL17]
Jérôme Durand-Lose. Ways to Compute in Euclidean Frameworks. In Matthew J. Patitz and Mike Stannett, editors, Unconventional Computation and Natural Computation - 16th International Conference, UCNC 2017, Fayetteville, AR, volume 10240 of LNCS, pages 8--25. Springer, 2017. [ bib | DOI | slides.pdf ]
This tutorial presents what kind of computation can be carried out inside a Euclidean space with dedicated primitives---and discrete or hybrid (continuous evolution between discrete transitions) time scales. The presented models can perform Classical (Turing, discrete) computations as well as, for some, hyper and analog computations (thanks to the continuity of space). The first half of the tutorial presents three models of computation based on respectively: ruler and compass, local constraints and emergence of polyhedra/polytopes and piece-wise constant derivative. The other half concentrates on signal machines: line segments are extended and replaced on meeting. These machines are capable hyper-computation and analog computation and to solve PSPACE-problem in “constant space and time” though partial fractal generation.

[BDL16]
Tom Besson and Jérôme Durand-Lose. Exact discretization of 3-speed rational signal machines. In Cellular Automata and Discrete Complex Systems - 22nd IFIP WG 1.5 International Workshop, AUTOMATA '16, volume 9664 of LNCS, pages 63--76. Springer, 2016. [ bib | DOI ]
[DL13]
Jérôme Durand-Lose. Irrationality is needed to compute with signal machines with only three speeds. In Paola Bonizzoni, Vasco Brattka, and Benedikt Löwe, editors, CiE '13, The Nature of Computation, number 7921 in LNCS, pages 108--119. Springer, 2013. Invited talk for special session Computation in nature. [ bib | DOI | http | slides | .pdf ]
Space-time diagrams of signal machines on finite configurations are composed of interconnected line segments in the Euclidean plane. As the system runs, a network emerges. If segments extend only in one or two directions, the dynamics is finite and simplistic. With four directions, it is known that fractal generation, accumulation and any Turing computation are possible. This communication deals with the three directions/speeds case. If there is no irrational ratio (between initial distances between signals or between speeds) then the network follows a mesh preventing accumulation and forcing a cyclic behavior. With an irrational ratio (here, the Golden ratio) between initial distances, it becomes possible to provoke an accumulation that generates infinitely many interacting signals in a bounded portion of the Euclidean plane. This behavior is then controlled and used in order to simulate a Turing machine and generate a 25-state 3-speed Turing-universal signal machine.

[DDLS12]
Denys Duchier, Jérôme Durand-Lose, and Maxime Senot. Computing in the fractal cloud: modular generic solvers for SAT and Q-SAT variants. In Manindra Agrawal, Barry S. Cooper, and Angsheng Li, editors, Theory and Applications of Models of Computations (TAMC '12), number 7287 in LNCS, pages 435--447. Springer, 2012. [ bib | DOI | http | .pdf ]
Abstract geometrical computation can solve hard combinatorial problems efficiently: we showed previously how Q-SAT —the satisfiability problem of quantified boolean formulae— can be solved in bounded space and time using instance-specific signal machines and fractal parallelization. In this article, we propose an approach for constructing a particular generic machine for the same task. This machine deploys the Map/Reduce paradigm over a discrete fractal structure. Moreover our approach is modular: the machine is constructed by combining modules. In this manner, we can easily create generic machines for solving satifiability variants, such as SAT, #SAT, MAX-SAT.

[DL11]
Jérôme Durand-Lose. Geometrical accumulations and computably enumerable real numbers (extended abstract). In Cristian S. Calude, Jarkko Kari, Ion Petre, and Grzegorz Rozenberg, editors, Int. Conf. Unconventional Computation 2011 (UC '11), number 6714 in LNCS, pages 101--112. Springer, 2011. [ bib | DOI | slides | .pdf ]
Abstract geometrical computation involves drawing colored line segments (traces of signals) according to rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. Time and space are continuous and accumulations can be devised to unlimitedly accelerate a computation and provide, in a finite duration, exact analog values as limits.

In the present paper, we show that starting with rational numbers for coordinates and speeds, the time of any accumulation is a c.e. (computably enumerable) real number and moreover, there is a signal machine and an initial configuration that accumulates at any c.e. time. Similarly, we show that the spatial positions of accumulations are exactly the d-c.e. (difference of computably enumerable) numbers. Moreover, there is a signal machine that can accumulate at any c.e. time or d-c.e. position.

[DDLS10]
Denys Duchier, Jérôme Durand-Lose, and Maxime Senot. Fractal parallelism: Solving SAT in bounded space and time. In Cheong Otfried, Kyung-Yong Chwa, and Kunsoo Park, editors, Int. Symp. on Algorithms and Computation (ISAAC '10), number 6506 in LNCS, pages 279--290. Springer, 2010. [ bib | DOI | .pdf ]
Abstract geometrical computation can solve NP-complete problems efficiently: any boolean constraint satisfaction problem, instance of SAT, can be solved in bounded space and time with simple geometrical constructions involving only drawing parallel lines on a Euclidean space-time plane. Complexity as the maximal length of a sequence of consecutive segments is quadratic. The geometrical algorithm achieves massive parallelism: an exponential number of cases are explored simultaneously. The construction relies on a fractal pattern and requires the same amount of space and time independently of the SAT formula.

[DL09]
Jérôme Durand-Lose. Abstract geometrical computation and computable analysis. In José Félix Costa and Nachum Dershowitz, editors, Int. Conf. on Unconventional Computation 2009 (UC '09), number 5715 in LNCS, pages 158--167. Springer, 2009. [ bib | DOI | slides | .pdf ]
[DL07]
Jérôme Durand-Lose. Abstract Geometrical Computation and the Linear Blum, Shub and Smale Model. In Barry S. Cooper, Benedikt. Löwe, and Andrea Sorbi, editors, Computation and Logic in the Real World, 3rd Conf. Computability in Europe (CiE 2007), number 4497 in LNCS, pages 238--247. Springer, 2007. [ bib | DOI | slides | .pdf ]
Abstract geometrical computation naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling at constant speed in a continuous space in continuous time. When signals collide, they are replaced by new signals according to some collision rules. This simple dynamics relies on real numbers with exact precision and is already known to be able to carry out any (discrete) Turing-computation. The Blum, Shub and Smale (BSS) model is famous for computing over (considered here as a unlimited register machine) by performing algebraic computations.

We prove that signal machines (set of signals and corresponding rules) and the infinite-dimension linear (multiplications are only by constants) BSS machines can simulate one another.

[DL06b]
Jérôme Durand-Lose. Reversible conservative rational abstract geometrical computation is Turing-universal. In Arnold Beckmann and John V. Tucker, editors, Logical Approaches to Computational Barriers, 2nd Conf. Computability in Europe (CiE '06), number 3988 in LNCS, pages 163--172. Springer, 2006. [ bib | DOI | slides | .pdf ]
In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability. In the present paper, we prove the Turing computing capability of reversible conservative abstract geometrical computation. Reversibility allows backtracking as well as saving energy; it corresponds here to the local reversibility of collisions. Conservativeness corresponds to the preservation of another energy measure ensuring that the number of signals remains bounded. We first consider 2-counter automata enhanced with a stack to keep track of the computation. Then we built a simulation by reversible conservative rational signal machines.

[DL06a]
Jérôme Durand-Lose. Forcasting black holes in abstract geometrical computation is highly unpredictable. In J.-Y. Cai, Barry S. Cooper, and Angshen Li, editors, Theory and Applications of Models of Computations (TAMC '06), number 3959 in LNCS, pages 644--653. Springer, 2006. [ bib | DOI | slides | .pdf ]
In Abstract geometrical computation for black hole computation (MCU '04, LNCS 3354), the author provides a setting based on rational numbers, abstract geometrical computation, with super-Turing capability: any recursively enumerable set can be decided in finite time. To achieve this, a Zeno-like construction is used to provide an accumulation similar in effect to the black holes of the black hole model.

We prove here that forecasting an accumulation is Σ02-complete (in the arithmetical hierarchy) even if only energy conserving signal machines are addressed (as in the cited paper). The Σ02-hardness is achieved by reducing the problem of deciding whether a recursive function (represented by a 2-counter automaton) is strictly partial. The Σ02-membership is proved with a logical characterization.

[DL05b]
Jérôme Durand-Lose. Abstract geometrical computation: Turing computing ability and undecidability. In Barry S. Cooper, Benedikt Löwe, and Leen Torenvliet, editors, New Computational Paradigms, 1st Conf. Computability in Europe (CiE '05), number 3526 in LNCS, pages 106--116. Springer, 2005. [ bib | DOI | slides | .pdf ]
[DL05a]
Jérôme Durand-Lose. Abstract geometrical computation for black hole computation (extended abstract). In M. Margenstern, editor, Machines, Computations, and Universality (MCU '04), number 3354 in LNCS, pages 176--187. Springer, 2005. [ bib | DOI | slides | .pdf ]
[DL01]
Jérôme Durand-Lose. Representing reversible cellular automata with reversible block cellular automata. In Robert Cori, Jacques Mazoyer, Michel Morvan, and Rémy Mosseri, editors, Discrete Models: Combinatorics, Computation, and Geometry, DM-CCG '01, volume AA of Discrete Mathematics and Theoretical Computer Science Proceedings, pages 145--154, 2001. [ bib | .html | slides | .pdf ]
Cellular automata are mappings over infinite lattices such that each cell is updated according to the states around it and a unique local function. Block permutations are mappings that generalize a given permutation of blocks (finite arrays of fixed size) to a given partition of the lattice in blocks. We prove that any d-dimensional reversible cellular automaton can be expressed as the composition of d+1 block permutations. We built a simulation in linear time of reversible cellular automata by reversible block cellular automata (also known as partitioning CA and CA with the Margolus neighborhood) which is valid for both finite and infinite configurations. This proves a 1990 conjecture by Toffoli and Margolus (Physica D 45) improved by Kari in 1996 (Mathematical System Theory 29).

[DL98b]
Jérôme Durand-Lose. Randomized uniform self-stabilization mutual exclusion. In A. Bui and V. Villain, editors, Distributed computing (OPODIS '98), pages 89--98. Hermes, 1998. [ bib | .pdf ]
[DL98a]
Jérôme Durand-Lose. About the universality of the billiard ball model. In M. Margenstern, editor, Universal Machines and Computations (UMC '98), volume 2, pages 118--133. Université de Metz, 1998. [ bib | .pdf ]
[DL97]
Jérôme Durand-Lose. Intrinsic Universality of a 1-Dimensional Reversible Cellular Automaton. In STACS 1997, number 1200 in LNCS, pages 439--450. Springer, 1997. [ bib | DOI | .pdf ]
This paper deals with simulation and reversibility in the context of Cellular Automata (CA). We recall the definitions of CA and of the Block (BCA) and Partitioned (PCA) subclasses. We note that PCA simulate CA. A simulation of reversible CA (RCA) with reversible PCA is built contradicting the intuition of known undecidability results. We build a 1d-RCA which is intrinsically universal, i.e., able to simulate any 1d-R-CA.

[DL95]
Jérôme Durand-Lose. Reversible Cellular Automaton Able to Simulate Any Other Reversible One Using Partitioning Automata. In LATIN 1995, number 911 in LNCS, pages 230--244. Springer, 1995. [ bib | DOI | .pdf ]
Partitioning automata (PA) are defined. They are equivalent to cellular automata (CA). Reversible sub-classes are also equivalent. A simple, reversible and universal partitioning automaton is described. Finally, it is shown that there are reversible PA and CA that are able to simulate any reversible PA or CA on any configuration. The resutls work in dimention 2 and above.

[DDLT94]
Marc Daumas, Jérôme Durand-Lose, and Louis-Pascal Tock. High speed implementation of a cellular automaton. In XIV Int. Conf. of the Chilean Computer Science Society, pages 283--294, 1994. [ bib | .pdf ]

Workshops internationaux (éventuellement sans publication)

[DDLS11b]
Denys Duchier, Jérôme Durand-Lose, and Maxime Senot. Solving Q-SAT in bounded space and time by geometrical computation. In Hristo Ganchev, Benedikt Löwe, Dag Normann, Ivan Soskov, and Mariya Soskova, editors, Models of computability in contecxt, 7th Int. Conf. Computability in Europe (CiE '11) (abstracts and handout booklet), pages 76--86. St. Kliment Ohridski University Press, Sofia University, 2011. [ bib | slides | .pdf ]
Abstract geometrical computation can solve PSPACE-complete problems efficiently: any quantified boolean formula, instance of Q-SAT -- the problem of satisfiability of quantified boolean formula -- can be decided in bounded space and time with simple geometrical constructions involving only drawing parallel lines on an Euclidean space-time. Complexity as the maximal length of a sequence of consecutive segments is quadratic. We use the continuity of the real line to cover all the possible boolean valuations by a recursive tree structure relying on a fractal pattern: an exponential number of cases are explored simultaneously by a massive parallelism.

[DDLS11a]
Denys Duchier, Jérôme Durand-Lose, and Maxime Senot. Computing with signals: a generic and modular signal machine for satisfiability problems. Workshop New Worlds of Computation (NWC '11), May 23--24, 2011, 2011. [ bib | http | .pdf ]
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.

[DL11]
Jérôme Durand-Lose. Introducing fractal computation. Lecture at Coping with complexity (COPCOM '11), 19, 20 oct., Cluj, Roumanie, 2011. [ bib | http | .pdf ]
For many problems, like the the Boolean constraint satisfaction problem (SAT), verifying any solution is quite simple while finding one is almost not feasible. Massive parallelism provides a way to test many potential solutions simultaneously but fail when the number of them grows exponentially with the size of the instance to solve. Fractal parallelism proposes a way to cope with this by dispatching this exponential numbers of trials on the first levels of a fractal. Building fractals is not meant to be done on nowadays computers, it relies on an idealization of collision computing: abstract geometrical computation where space and time are continuous and can be effectively subdivided ad libidum; which we introduce.

[DDLS10]
Denys Duchier, Jérôme Durand Lose, and Maxime Senot. Massively Parallel Automata in Euclidean Space-Time. In First International Workshop on Spatial Computing (SCW '10), a SASO '10 satellite workshop, Budapest Hongrie, 2010. [ bib | http | .pdf ]
In the cellular automata (CA) literature, discrete lines in discrete space-time diagrams are often idealized as Euclidean lines in order to design CA or analyze their dynamic behavior. In this paper, we present a parallel model of computation corresponding to this idealization: dimensionless particles move uniformely at fixed velocities along the real line and are transformed when they collide. Like CA, this model is parallel, uniform in space-time and uses local updating. The main difference is the use of the continuity of space and time, which we proceed to illustrate with a construction to solve Q-SAT, the satisfiability problem for quantified boolean formulae, in bounded space and time, and quadratic collision depth.

[DL10b]
Jérôme Durand-Lose. A reversible and conservative model based on rational signal machines for black hole computation. In Mike Stannett, editor, HyperNet 10: The Unconventional Computation 2010 (UC '2010) Hypercomputation Workshop, pages 48--59, 2010. [ bib | slides | .pdf ]
In the context of Abstract geometrical computation, it has been proved that black hole model (and SAD computers) can be implemented. To be more physic-like, it would be interesting that the construction is reversible and preserves some energy. There is already a (energy) conservative and reversible two-counter automaton simulation.

In the present paper, based on reversible and conservative stacks, reversible Turing machines are simulated. Then a shrinking construction that preserves these properties is presented. All together, a black hole model implementation that is reversible and conservative (both the shrinking structure and the universal Turing machine) is provided.

[DL10a]
Jérôme Durand-Lose. The coordinates of isolated accumulations [includes] computable real numbers. In Fernando Ferreira, Hélia Guerra, Elvira Mayordomo, and João Rasga, editors, Programs, Proofs, Processes, 6th Int. Conf. Computability in Europe (CiE '10) (abstracts and extended abstracts of unpublished papers), pages 158--167. CMATI, U. Azores, 2010. Contains a flaw, corrected in [DL11]. [ bib | slides | .pdf ]
This paper has a flaw. Please look at the corrected version: [?] Jérôme Durand-Lose. Geometrical accumulations and computably enumerable real numbers (extended abstract). In Cristian S. Calude, Jarkko Kari, Ion Petre, and Grzegorz Rozenberg, editors, Int. Conf. Unconventional Computation 2011 (UC '11), number 6714 in LNCS, pages 101-112. Springer, 2011.

In Abstract geometrical computation, Turing computability is provided by simples machines involving drawing colored line segments, called signals, accordin g to simple rules: signals with similar color are parallel and when they intersect, they are replaced according to their colors. These signal machines also provide a very powerful model of analog computation following both the approaches of computable analysis and of Blum, Shub and S male. The key is that accumulations can be devised to accelerate the computation and provide an exact analog values as limits in finite time.

In the present paper, we show that starting with rational numbers for coordinates and speeds, the collections of positions of accumulations in both space and time are exactly the computable real numbers (as defined by computable analysis). Moreover, there is a signal machine that can provide an accumulation at any computable place and date.

[DL08c]
Jérôme Durand-Lose. The Signal Point of View: From Cellular Automata to Signal Machines. In Bruno Durand, editor, Journées Automates cellulaires (JAC '08), pages 238--249, 2008. [ bib | slides | .pdf ]
[DL08d]
Jérôme Durand-Lose. Small Turing universal signal machines. In Turlough Neary, Anthony Seda, and Damien Woods, editors, International Workshop on the Complexity of Simple Programs, Cork, Ireland, December 6-7, pages 89--102. Cork University Press, 2008. [ bib | slides | .pdf ]
[DL08b]
Jérôme Durand-Lose. Black hole computation: implementation with signal machines. In C. S. Calude and J. F. Costa, editors, International Workshop Physics and Computation, Wien, Austria, Agust 25-28, Research Report CDMTCS-327, pages 136--158, 2008. [ bib | slides | .pdf ]
[DL08a]
Jérôme Durand-Lose. Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model. In Arnold Beckmann, Costas Dimitracopoulos, and Benedikt Löwe, editors, Logic and Theory of Algorithms, 4th Conf. Computability in Europe (CiE '08) (abstracts and extended abstracts of unpublished papers), pages 107--116. University of Athens, 2008. [ bib | slides | .pdf ]
Abstract geometrical computation (AGC) naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling and colliding. It can carry out any Turing computation, but since it works with continuous time and space, some analog computing capability exists. In Abstract Geometrical Computation and the Linear BSS Model (CiE 2007, LNCS 4497, p. 238-247), it is shown that AGC without any accumulation has the same computing capability as the linear BSS model.

An accumulation brings infinitely many time steps in a finite duration. This has been used to implement the black-hole model of computation (Fundamenta Informaticae 74(4), p. 491-510). It also makes it possible to multiply two variables, thus simulating the full BSS. Nevertheless a BSS uncomputable function, the square root, can also be implemented, thus proving that the computing capability of AGC with isolated accumulations is strictly beyond the one of BSS.

[DL05]
Jérôme Durand-Lose. Abstract geometrical computation for black hole computation. In Computations on the continuum, Lisboa, June 28-29 2005, 2005. [ bib | .pdf ]
[DL03]
Jérôme Durand-Lose. Geometric computation on the plane---signal machines. In Exystence Thematic Institute --- Discrete and Computational Aspects of Complex Systems, LIP, June 2003, 2003. [ bib | .pdf ]
[DL98]
Jérôme Durand-Lose. Cellular automata, block CA, partition CA reversibility and simulation. In V. Bruyère, editor, Journés montoises, Mons (Belgique), March 1998. [ bib ]
[DL97]
Jérôme Durand-Lose. Cellular automata, block CA, partitioned CA, reversibility and simulation. In Cellular Automata Workshop 1997, Gargnano (Italie), September 1997. [ bib ]
[DL96]
Jérôme Durand-Lose. Sand dripping in linear space. In Cellular Automata Workshop '96, pages 14--16, Schloß Rauischholzhauen, March 1996. [ bib ]

Workshops nationaux (éventuellement sans publication)

[DL13]
Jérôme Durand-Lose. Irrationality is needed to compute with signal machines with only three speeds. FRAC d'hivers, Montpellier, February28 2013. [ bib | .pdf ]
[DL12]
Jérôme Durand-Lose. Signal machines: localization of isolated accumulation. Journées Calculabilités, U. Paris 7, March5 and 6, 2012. [ bib | .html | .pdf ]
Signal machines can be seen as a way to automatically extends a drawing consisting of line segments in Euclidean spaces. Dealing with a continuous setting, accumulation points might occur. We characterize exactly the possible localizations of accumulation points as enumerable computable real and difference of such. These reals are natural extension of computable reals of computable analysis.

[DLLS11]
Jérôme Durand-Lose, Vincent Levorato, and Maxime Senot. Machines à signaux: origine, puissance, retour au raisonnable. Journée Spacial Computing, LRI, Orsay, May5 2011. [ bib | .pdf ]
L'exposé commencera par montrer la présence et l'utilisation de signaux dans les automates cellulaires et le désir de s'affranchir de la lourdeur du discret. Dans un second temps, nous montrons la puissance du modèle en montrant comment résoudre QSAT de façon générique. Enfin dans un troisième temps, nous essaierons de nous éloigner de l'utopie d'un espace et d'un temps continus et re-découpable ad infinitum en tentant de discrétiser automatiquement (grace à la pré-topologie).

[DDLS10]
Denys Duchier, Jérôme Durand-Lose, and Maxime Senot. Construction géométrique pour résoudre SAT en temps constant. Journée Informatique Région Centre (JIRC '09), 22 janvier 2010, 2010. [ bib | .pdf ]
[DL05]
Jérôme Durand-Lose. Autostabilisation: de l'exclusion mutuelle sur un anneau à l'élection d'un chef sur un graphe quelconque. Journée Informatique Région Centre (JIRC '05), June29 and 30 2005. [ bib | résumé | .pdf ]
[DL02]
Jérôme Durand-Lose. Signaux libres. 4èmes Journées nationales Systèmes Dynamiques Discrets, June 2002. [ bib | .pdf ]
[DL98]
Jérôme Durand-Lose. Automates cellulaires, réversibilité et universalité. Journées Montoises '98, 1998. [ bib | .pdf ]
[DL96b]
Jérôme Durand-Lose. Universalité intrinsèque au sein des automates cellulaires partitionnés réversibles. Rencontre Mosydis (GdR-PrC AMI), ÉNS Cachan, November 1996. [ bib ]
[DL96a]
Jérôme Durand-Lose. Simulation espace-temps réversible d'automates cellulaires non-réversibles. École d'automne du GRD-PRC AMI, Nice, September 1996. [ bib | .pdf ]

Rapports de recherches non publiés

[DL96b]
Jérôme Durand-Lose. Sand piles in digraphs. Research Report 1113--96, LaBRI, Université Bordeaux I, 33405 Talence Cedex, France, 1996. [ bib | .pdf ]
[DL96a]
Jérôme Durand-Lose. Any reversible cellular automaton can be represented with block permutations. Research Report 1135-96, LaBRI, 1996. [ bib | .pdf ]

Médiatisation

[BSM+12]
Gabriel Bergounioux, Emmanuel Schang, Denis Maurel, Agata Savary, Jérôme Durand-Lose, and Yannick Parmentier. L'ordinateur et les langues, January 2012. Covalences 82 (2012). [ bib | http ]

Soumis

[BCDL+13]
Florent Becker, Mathieu Chapelle, Jérôme Durand-Lose, Vincent Levorato, and Maxime Senot. Abstract geometrical computation 8: Small machines, accumulations & rationality. Submitted, 2013. [ bib | http ]

Copyrights for some of the papers below have been transfered, or will be transfered to various publishers of journals, conferences proceedings, etc. For such papers I am required to post the following notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. Publisher's copyright policy are available at © SIAM, © ACM, © Springer, © Elsevier, © Ideal, © King's College....
Last modified: Sun May 20 14:10:50 CEST 2007