@unpublished{durand-lose23ucnc,
pdf = {Publications/2023_UCNC.pdf},
slides = {Publications/2023_UCNC_poster.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Drawing numerable linear orderings},
note = {Poster presented at the 16th Int. Conf. Unconventional
{C}omputation and {N}atural {C}omputation, {UCNC}
2023, Jacksonville, FL, USA},
year = {2023},
language = {english},
hal = {https://hal.science/hal-04355447}
}
@proceedings{durand-lose+vaszil22mcu,
editor = {Durand{-}Lose, J{\'{e}}r{\^{o}}me and
Vaszil, Gy{\"{o}}rgy},
title = {Machines, Computations, and Universality - 9th International Conference,
{MCU} 2022, Debrecen, Hungary},
series = {LNCS},
volume = {13419},
publisher = {Springer},
year = {2022},
doi = {10.1007/978-3-031-13502-6},
isbn = {978-3-031-13501-9},
hal = {https://hal.science/hal-03765155v1}
}
@inproceedings{durand-lose22dcfs,
author = {Durand{-}Lose, J{\'{e}}r{\^{o}}me},
editor = {Han, Yo{-}Sub and
Vaszil, Gy{\"{o}}rgy},
title = {On the Power of Recursive Word-Functions Without Concatenation},
booktitle = {Descriptional Complexity of Formal Systems - 24th {IFIP} {WG} 1.02
International Conference, {DCFS} 2022, Debrecen, Hungary},
series = {LNCS},
volume = {13439},
pages = {30--42},
publisher = {Springer},
year = {2022},
doi = {10.1007/978-3-031-13257-5\_3},
pdf = {Publications/2022_DCFS.pdf},
slides = {Publications/2022_DCFS_slides.pdf},
abstract = {Primitive recursion can be defined on words instead of
natural numbers. Up to usual encoding, primitive
recursive functions coincide. Working with words
allows to address words directly and not through
some integer encoding (of exponential size).
Considering alphabets with at least two symbols
allows to relate simply and naturally to complexity
theory. Indeed, the polynomial-time complexity
class (as well as \classNP and exponential time)
corresponds to delayed and dynamical evaluation with
a polynomial bound on the size of the trace of the
computation as a direct acyclic graph.
Primitive
recursion in the absence of concatenation (or
successor for numbers) is investigated. Since only
suffixes of an input can be output, computation is
very limited; \eg pairing and unary encoding are
impossible. Yet non-trivial relations and languages
can be decided. Some algebraic
($\mathtt{a}^n\mathtt{b}^n$, palindromes) and
non-algebraic
($\mathtt{a}^n\mathtt{b}^n\mathtt{c}^n$) languages
are decidable. It is also possible to check
arithmetical constrains like
$\mathtt{a}^n\mathtt{b}^m\mathtt{c}^{P(n,m)}$ with
$P$ polynomial with positive coefficients in two (or
more) variables. Every regular language is
decidable if recursion can be defined on multiple
functions at once.},
keywords = {Primitive recursion; Recursion on words; String
recursion; Word-Functions},
hal = {https://hal.science/hal-03765152v1}
}
@unpublished{durand-lose+hoogeboom+jonoska22arxiv,
arxiv = {https://arxiv.org/abs/2202.05165},
author = {Durand-Lose, J{\'e}r{\^o}me and
Hoogeboom, Hendrik Jan and
Jonoska, Nata\v{s}a},
title = {Deterministic Non-cooperative Binding in Two-Dimensional Tile Assembly Systems Must Have Ultimately Periodic Paths},
note = {arXiv 2202.05165, 26 pages},
year = {2022},
abstract = {We consider non-cooperative binding, so-called
'temperature 1', in deterministic or directed
(called here confluent) tile self-assembly systems
in two dimensions and show a necessary and
sufficient condition for such system to have an
ultimately periodic assembly path. We prove that an
infinite maximal assembly has an ultimately periodic
assembly path if and only if it contains an infinite
assembly path that does not intersect a periodic
path in the Z2 grid. Moreover we show that every
infinite assembly must satisfy this condition, and
therefore, contains an ultimately periodic
path. This result is obtained through a
super-position and a combination of two paths that
produce a new path with desired properties, a
technique that we call co-grow of two paths. The
paper is an updated and improved version of the
first part of arXiv 1901.08575.},
keywords = {Tile assembly system; Directed (confluent) system;
Non-cooperation; Ultimately periodic}
}
@article{durand-lose+emmanuel21tcs,
doi = {10.1016/j.tcs.2021.06.009},
arxiv = {https://arxiv.org/abs/2106.11176},
hal = {https://hal.science/hal-03266838},
pdf = {Publications/2021_TCS.pdf},
note = {arXiv 2106.11176},
author = {Durand-Lose, J{\'e}r{\^o}me and
Emmanuel, Aur{\'e}lien},
title = {Abstract Geometrical Computation 11: Slanted Firing
Squad Synchronisation on Signal Machines},
journal = {Theoret Comp Sci},
year = {2021},
volume = {894},
pages = {103--120},
language = {english},
abstract = {Firing Squad Synchronisation on Cellular Automata is the
dynamical synchronisation of finitely many cells
without any prior knowledge of their range. This
can be conceived as a signal with an infinite speed.
Most of the proposed constructions naturally
translate to the continuous setting of signal
machines and generate fractal figures with an
accumulation on a horizontal line,
i.e. synchronously, in the space-ti me diagram.
Signal machines are studied in a series of articles
named Abstract Geometrical Computation.\par In the
present article, we design a signal machine that is
able to synchronise/accumulate on any non-infinite
slope. The slope is encoded in the initial
configuration. This is done by constructing an
infinite tree such that each node computes the way
the tree expands.\par The interest of Abstract
Geometrical computation is to do away with the
constraint of discrete space, while tackling new
difficulties from continuous space. The interest of
this paper in particular is to provide basic tools
for further study of computable accumulation lines
in the signal machine model.},
keywords = {Abstract Geometrical Computation; Cellular Automata;
Divide and Conquer; Firing Squad Synchronisation;
Fractal; Signal Machines}
}
@article{becker+besson+durand-lose+emmanuel+foroughmand-araabi+goliaei+heydarshahi21,
doi = {10.1145/3442359},
arxiv = {https://arxiv.org/abs/1804.09018},
hal = {https://hal.science/hal-03126362},
pdf = {Publications/2020_ToCT.pdf},
author = {Becker, Florent and
Besson, Tom and
Durand-Lose, J{\'e}r{\^o}me and
Emmanuel, Aur{\'e}lien and
Foroughmand-Araabi, Mohammad-Hadi and
Goliaei, Sama and
Heydarshahi, Shahrzad},
title = {Abstract Geometrical Computation 10: An Intrinsically Universal Family of Signal Machines},
journal = {ACM Trans. Comput. Theory},
year = {2021},
volume = {13},
number = {1},
pages = {1--31},
note = {arXiv 1804.09018},
language = {english},
abstract = {Signal machines form an abstract and idealised model of
collision computing. Based on dimensionless signals
moving on the real line, they model particle/signal
dynamics in Cellular Automata. Each particle, or
signal, moves at constant speed in continuous time
and space. When signals meet, they get replaced by
other signals. A signal machine defines the types of
available signals, their speeds and the rules for
replacement in collision.\par A signal machine A
simulates another one B if all the space-time
diagrams of B can be generated from space-time
diagrams of A by removing some signals and renaming
other signals according to local information. Given
any finite set of speeds S, we construct a signal
machine that is able to simulate any signal machine
whose speeds belong to S. Each signal is simulated
by a macro-signal, a ray of parallel signals. Each
macro-signal has a main signal located exactly where
the simulated signal would be, as well as auxiliary
signals which encode its id and the collision rules
of the simulated machine.\par The simulation of a
collision, a macro-collision, consists of two
phases. In the first phase, macro-signals are
shrunk, then the macro-signals involved in the
collision are identified and it is ensured that no
other macro-signal comes too close. If some do, the
process is aborted and the macro-signals are shrunk,
so that the correct macro-collision will eventually
be restarted and successfully initiated. Otherwise,
the second phase starts: the appropriate collision
rule is found and new macro-signals are generated
accordingly.\par Considering all finite set of
speeds S and their corresponding simulators provides
an intrinsically universal family of signal
machines.},
keywords = {Abstract Geometrical Computation; Collision computing;
Intrinsic universality; Signal machine; Simulation}
}
@article{durand-lose+kari+verlan21fi-mcu,
doi = {10.3233/FI-2021-2052},
hal = {},
title = {Special issue on {M}achines, {C}omputations and {U}niversality ({MCU}~2018)},
volume = {181},
number = {2-3},
year = {2021},
publisher = {IOS Press},
journal = {Fund Inf},
author = {Durand-Lose, J{\'e}r{\^o}me and Kari, Jarkko and Verlan, Sergey},
pages = {1--271},
language = {english}
}
@article{durand-lose+hendricks+patitz+perkins+sharp20naco_dna,
doi = {10.1007/s11047-019-09751-9},
arxiv = {https://arxiv.org/abs/1807.04818},
hal = {https://hal.science/hal-02178978},
author = {Durand-Lose, J\'er\^ome and
Hendricks, Jacob and
Patitz, Matthew and
Perkins, Ian and
Sharp, Michael},
journal = {Nat Comput},
title = {Self-assembly of 3-{D} structures using 2-{D} folding tiles},
volume = {19},
number = {2},
pages = {337--355},
year = {2020},
publisher = {Springer},
language = {english},
abstract = {Self-assembly is a process which is ubiquitous in
natural, especially biological systems. It occurs
when groups of relatively simple components
spontaneously combine to form more complex
structures. While such systems have inspired a large
amount of research into designing theoretical models
of self-assembling systems, and even
laboratory-based implemen- tations of them, these
artificial models and systems often tend to be
lacking in one of the powerful features of natural
systems (e.g. the assembly and folding of proteins),
which is dynamic reconfigurability of structures. In
this paper, we present a new mathematical model of
self-assembly, based on the abstract Tile Assembly
Model (aTAM), called the Flexible Tile Assembly
Model (FTAM). In the FTAM, the individual components
are 2-dimensional tiles as in the aTAM, but in the
FTAM, bonds between the edges of tiles can be
flexible, allowing bonds to flex and entire
structures to reconfigure, thus allowing
2-dimensional components to form 3-dimensional
structures. We analyze the powers and limitations of
FTAM systems by (1) demonstrating how flexibility
can be controlled to carefully build desired
structures, and (2) showing how flexibility can be
beneficially harnessed to form structures which can
‘‘efficiently’’ reconfigure into many different
configurations and/or greatly varying
configurations. We also show that with such power
comes a heavy burden in terms of computational
complexity of simulation and prediction by proving
that for important properties of FTAM systems,
determining their existence is intractable, even for
properties which are easily computed for systems in
less dynamic models.},
keywords = {Self-assembly; 3-Dimensional; Folding; Reconfiguration}
}
@unpublished{durand-lose+hoogeboom+jonoska19arxiv,
arxiv = {https://arxiv.org/abs/1901.08575},
author = {Durand-Lose, J{\'e}r{\^o}me and
Hoogeboom, Hendrik Jan and
Jonoska, Nata\v{s}a},
title = {Deterministic 2-Dimensional Temperature-1 Tile Assembly Systems Cannot Compute},
note = {arXiv 1901.08575, 50 pages},
year = {2019},
abstract = {We consider non-cooperative binding, so-called
`temperature 1', in deterministic or directed
(called here {\it confluent}) tile self-assembly
systems in two dimensions and show a necessary and
sufficient condition for such system to have an
ultimately periodic assembly path. We prove that an
infinite maximal assembly has an ultimately periodic
assembly path if and only if it contains an infinite
assembly path that does not intersect a periodic
path in the $\mathbb{N}^2$ grid. Moreover we show
that every infinite assembly must satisfy this
condition and therefore contain an ultimately
periodic path.\par This result is obtained through a
superposition and a combination of two paths that
produce a new path with desired properties, a
technique that we call {\it co-grow} of two paths.},
keywords = {Tile assembly system; Directed (confluent) system;
Non-cooperation; Ultimately periodic}
}
@inproceedings{durand-lose+hendricks+patitz+perkins+sharp18dna,
doi = {10.1007/978-3-030-00030-1_7},
arxiv = {https://arxiv.org/abs/1807.04818},
hal = {https://hal.science/hal-01828641},
author = {Durand-Lose, J\'er\^ome and
Hendricks, Jacob and
Patitz, Matthew and
Perkins, Ian and
Sharp, Michael},
series = {LNCS},
title = {Self-{A}ssembly of 3-D {S}tructures {U}sing 2-D {F}olding {T}iles},
booktitle = {DNA~24},
pages = {105--121},
editor = {Doty, David and
Dietz, Hendrik},
volume = {11145},
year = {2018},
publisher = {Springer},
language = {english},
abstract = {Self-assembly is a process which is ubiquitous in
natural, especially biological systems. It occurs
when groups of relatively simple components
spontaneously combine to form more complex
structures. While such systems have inspired a large
amount of research into designing theoretical models
of self-assembling systems, and even
laboratory-based implementations of them, these
artificial models and systems often tend to be
lacking in one of the powerful features of natural
systems (e.g. the assembly and folding of proteins),
namely the dynamic reconfigurability of
structures. In this paper, we present a new
mathematical model of self-assembly, based on the
abstract Tile Assembly Model (aTAM), called the
Flexible Tile Assembly Model (FTAM). In the FTAM,
the individual components are 2-dimensional square
tiles as in the aTAM, but in the FTAM, bonds between
the edges of tiles can be flexible, allowing bonds
to flex and entire structures to reconfigure, thus
allowing 2-dimensional components to form
3-dimensional structures. We analyze the powers and
limitations of FTAM systems by (1) demonstrating how
flexibility can be controlled to carefully build
desired structures, and (2) showing how flexibility
can be beneficially harnessed to form structures
which can “efficiently” reconfigure into many
different configurations and/or greatly varying
configurations. We also show that with such power
comes a heavy burden in terms of computational
complexity of simulation and prediction by proving
that, for important properties of FTAM systems,
determining their existence is intractable, even for
properties which are easily computed for systems in
less dynamic models.}
}
@article{becker+chapelle+levorato+durand-lose+senot18jcss,
doi = {10.1016/j.jcss.2018.06.001},
arxiv = {http://arxiv.org/abs/1307.6468},
hal = {https://hal.science/hal-01828619},
author = {Becker, Florent and Chapelle, Mathieu and Durand-Lose, J{\'e}r{\^o}me and Levorato, Vincent and Senot, Maxime},
title = {Abstract geometrical computation 8{:} {S}mall {M}achines, {A}ccumulations \& {R}ationality},
journal = {J~Comput System Sci},
year = {2018},
volume = {97},
pages = {182--198},
language = {english},
abstract = {In the context of abstract geometrical computation,
computing with coloured line segments, we consider
the possibility of an accumulation\,---topologycal
limit point of segment
intersections/collisions---\,with \emph{small}
signal machines, i.e. having only a very limited
number of distinct slopes/speeds when started with
finitely many segments/signals. The cases of $2$
and $4$ speeds are trivial: no machine can produce
an accumulation with only $2$ speeds and an
accumulation can be generated with $4$ speeds. The
main result is the twofold $3$-speed case. No
accumulation can happen when all ratios between
speeds and all ratios between initial distances are
rational. Accumulation is possible in the case of
an irrational ratio between two speeds or of an
irrational ratio between two distances in the
initial configuration. This dichotomy is explained
by the presence of a phenomenon computing Euclid's
$\gcd$ algorithm: it stops if and only if its input
is commensurable, i.e., of rational ratio.},
keywords = {Abstract Geometrical Computation; Accumulation;
Euclidean Geometry; Euclid's Algorithm; Signal
Machine; Unconventional Computing}
}
@proceedings{durand-lose+verlan18mcu,
doi = {10.1007/978-3-319-92402-1},
hal = {https://hal.science/hal-01792687},
url_conf = {https://mcu2018.lacl.fr/},
title = {Machines, {C}omputations and {U}niversality ({MCU}~2018)},
year = {2018},
publisher = {Springer},
series = {LNCS},
editor = {Durand-Lose, J{\'e}r{\^o}me and Verlan, Sergey},
number = {10881},
language = {english}
}
@incollection{durand-lose18rev-book,
doi = {10.1007/978-3-319-73216-9_4},
hal = {https://hal.science/hal-01792349},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Simulation and {I}ntrinsic {U}niversality {A}mong
{R}eversible {C}ellular {A}utomata, the {P}artition
{C}ellular {A}utomata {L}everage},
booktitle = {Reversibility and {U}niversality, Essays Presented to
{K}enichi {M}orita on the Occasion of his 70th
Birthday},
pages = {61--93},
editor = {Andrew Adamatzky},
series = {Emergence, Complexity and Computation},
number = {30},
publisher = {Springer},
year = {2018},
isbn = {978-3-319-73215-2},
language = {english},
abstract = {This chapter presents the use of Partitioned Cellular
Automata\,---{}intro\-duced by Morita and
colleagues---\,as the tool to tackle simulation and
intrinsic universality in the context of Reversible
Cellular Automata. \par Cellular automata (CA) are
mappings over infinite lattices such that all cells
are updated synchronously according to the states
around each one and a common local function. A CA is
reversible if its global function is invertible and
its inverse can also be expressed as a CA. Kari
proved in 1989 that invertibility is not decidable
(for CA of dimension at least $2$) and is thus hard
to manipulate. Partitioned Cellular Automata (PaCA)
were introduced as an easy way to handle
reversibility by partitioning the states of cells
according to the neighborhood. Another approach by
Margolus led to the definition of Block CA (BlCA)
where blocks of cells are updated
independently. Both models allow easy check and
design for reversibility. \par After proving that
CA, BlCA and PaCA can simulate each other, it is
proven that the reversible sub-classes can also
simulate each other contradicting the intuition
based on decidability results. In particular, it is
proven that any $d$-dimensional reversible CA
($d$-RCA) can be expressed as a BlCA with $d{+}1$
partitions. This proves a 1990 conjecture by Toffoli
and Margolus (\textit{Physica D} 45) improved and
partially proved by Kari in 1996
(\textit{Mathematical System Theory} 29). With the
use of signals and reversible programming, a 1-RCA
that is intrinsically universal\,---able to simulate
any 1-RCA---\,is built. Finally, with a peculiar
definition of simulation, it is proven that any CA
(reversible or not) can be simulated by a reversible
one. All these results extend to any dimension.},
keywords = {Block Cellular Automata; Cellular Automata; Intrinsic
Universality; Invertibility; Margolus neighborhood;
Partitioned Cellular Automata; Reversibility;
Reversible Cellular Automata}
}
@article{durand-lose+kari+nagy17fi-mcu,
doi = {10.3233/FI-2017-1573},
hal = {https://hal.science/hal-01621943},
title = {Special issue on {M}achines, {C}omputations and {U}niversality ({MCU}~2015)},
year = {2017},
publisher = {IOS Press},
journal = {Fund Inf},
author = {Durand-Lose, J{\'e}r{\^o}me and Kari, Jarkko and Nagy, Benedek},
volume = {155},
number = {1--2},
pages = {1--232},
language = {english}
}
@inproceedings{durand-lose17ucnc,
doi = {10.1007/978-3-319-58187-3_2},
hal = {https://hal.science/hal-01557281},
pdf = {Publications/2017_UCNC.pdf},
slides = {Publications/2017_UCNC_slides.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
series = {LNCS},
title = {Ways to {C}ompute in {E}uclidean {F}rameworks},
booktitle = {Unconventional {C}omputation and {N}atural {C}omputation - 16th Int.
Conf., {UCNC} 2017, Fayetteville, AR},
pages = {8--25},
editor = {Patitz, Matthew J. and
Stannett, Mike},
volume = {10240},
year = {2017},
publisher = {Springer},
language = {english},
abstract = {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.},
keywords = {Analog computation; Computability; Fractal computation;
Fractal generation; Hybrid-computation;
Hyper-computation; Mondrian Automata; Piece-wise
constant derivative; Ruler and compass; Signal
machine; Turing computation}
}
@article{besson+durand-lose17jca,
hal = {https://hal.science/hal-01298229},
author = {Besson, Tom and Durand-Lose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation 9{:} {E}xact {D}iscretization of 3-speed {R}ational {S}ignal {}Machines},
journal = {J~Cell Autom},
volume = {12},
number = {3--4},
pages = {159--187},
year = {2017},
language = {english},
abstract = {Firing Squad Synchronisation on Cellular Automata is the
dynamical synchronisation of finitely many cells
without any prior knowledge of their range. This
can be conceived as a signal with an infinite speed.
Most of the proposed constructions naturally
translate to the continuous setting of signal
machines and generate fractal figures with an
accumulation on a horizontal line,
i.e. synchronously, in the space-ti me diagram.
Signal machines are studied in a series of articles
named Abstract Geometrical Computation.\par In the
present article, we design a signal machine that is
able to synchronise/accumulate on any non-infinite
slope. The slope is encoded in the initial
configuration. This is done by constructing an
infinite tree such that each node computes the way
the tree expands.\par The interest of Abstract
Geometrical computation is to do away with the
constraint of discrete space, while tackling new
difficulties from continuous space. The interest of
this paper in particular is to provide basic tools
for further study of computable accumulation lines
in the signal machine model.},
keywords = {abstract geometrical computation; automatic
discretization; cellular automata; signal machines}
}
@inproceedings{besson+durand-lose16automata,
doi = {10.1007/978-3-319-39300-1_6},
hal = {https://hal.science/hal-01298378},
author = {Besson, Tom and Durand-Lose, J{\'e}r{\^o}me},
title = {Exact discretization of 3-speed rational signal machines},
series = {LNCS},
publisher = {Springer},
volume = {9664},
year = {2016},
booktitle = {Cellular Automata and Discrete Complex Systems - 22nd {IFIP} {WG}
1.5 International Workshop, {AUTOMATA~2016}},
pages = {63--76},
language = {english}
}
@incollection{durand-lose16ainuc,
hal = {https://hal.science/hal-01251455},
doi = {10.1007/978-3-319-33924-5_6},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Computing in {P}erfect {E}uclidean {F}rameworks},
booktitle = {Advances in {U}nconventional {C}omputing -- 1{:} {T}heory},
editor = {Adamatzky, Andrew},
series = {{E}mergence, {C}omplexity and {C}omputation},
number = {23},
pages = {141--163},
publisher = {Springer},
year = {2016},
language = {english},
abstract = {This chapter presents what kind of computation can be
carried out using an Euclidean space\,---as input,
memory, output...---\,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).\par 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.\par 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,
e.g., quantif ied SAT in ``constant space and
time''.},
keywords = {Analog computation; Computability; Fractal computation;
Fractal generation; Hybrid-computation;
Hyper-computation; Mondrian Automata; Piece-wise
constant derivative; Ruler and compass; Signal
machine; Turing computation}
}
@incollection{becker+durand-lose15ejcim,
hal = {https://hal.science/hal-01251468},
pdf = {Publications/2015_EJC_IM.pdf},
slides = {Publications/2015_EJC_IM_slides.pdf},
url_conf = {http://www.univ-orleans.fr/lifo/evenements/EJCIM2015/},
author = {Becker, Florent and Durand-Lose, J{\'e}r{\^o}me},
title = {Construire et calculer dans un monde 2{D}},
booktitle = {Informatique Math{\'e}matique --- une photographie en 2015},
editor = {Ollinger, Nicolas},
pages = {135--177},
publisher = {CNRS {\'e}dition},
year = {2015},
language = {english},
abstract = {Ce chapitre pr{\'e}sente ce qu’il est possible
d’accomplir dans un espace euclidien en
consid{\'e}rant justement cet espace (comme
entr{\'e}e, support, m{\'e}moire…). Accomplir {\`a}
la fois comme calculs (au sens discret, mais aussi
continu) et comme construction d’objet.\par Trois
mod{\`e}les de calcul bas{\'e}s sur des primitives
g{\'e}om{\'e}triques — l’utilisation de la r{\`e}gle
et du compas, l’{\'e}mergence de poly{\`e}dres ou
l’utilisation de d{\'e}riv{\'e}es constantes — sont
pr{\'e}sent{\'e}s.\par Les machines {\`a} signaux
sont ensuite d{\'e}finies : des segments de droite
sont prolong{\'e}s et, d{\`e}s qu’ils se
rencontrent, ils sont remplac{\'e}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 {\'e}galement
possibles. De plus, en contr{\^o}lant la
g{\'e}n{\'e}ration de fractales, le calcul fractal
permet de r{\'e}soudre SAT quantifi{\'e} en «~temps
et espace constant~». Finalement, les assemblages
autonomes d’{\'e}l{\'e}ments discrets dans le plan
forment un mod{\`e}le d’une grande
richesse. Celui-ci relie des objets th{\'e}oriques
et combinatoires que sont les pavages avec des
r{\'e}alisations possibles dans un mod{\`e}le
bio-informatique (calcul {\`a} ADN). Le calcul
obtenu est asynchrone, et la synchronisation se fait
par la g{\'e}om{\'e}trie. Temps et espace sont deux
dimensions fortement intriqu{\'e}es.},
keywords = {Automates de Mondrian; Bio-informatique; Asynchronisme;
Auto-assemblage; Calcul analogique; Calcul au sens
de Turing; Calcul fractal; Fractales; Hyper-calcul;
Machines {\`a} signaux; Pavages; Piecewise constant
derivative; R{\`e}gle et compas; Tuiles de Wang}
}
@proceedings{durand-lose+nagy15mcu,
doi = {10.1007/978-3-319-23111-2},
hal = {https://hal.science/hal-01202856},
title = {Machines, {C}omputations and {U}niversality ({MCU}~2015)},
year = {2015},
publisher = {Springer},
series = {LNCS},
editor = {Durand-Lose, J{\'e}r{\^o}me and Nagy, Benedek},
number = {9288},
language = {english}
}
@article{durand-lose+jonoska14naco-ucnc,
doi = {10.1007/s11047-014-9417-x},
hal = {https://hal.science/hal-00989257},
title = {Special issue on {U}nconventional {C}omputation and {N}atural {C}omputation ({UCNC}~2012)},
author = {Durand-Lose, J{\'e}r{\^o}me and Jonoska, Nata{\v{s}}a},
volume = {13},
number = {2},
pages = {193--283},
journal = {Nat Comput},
publisher = {Springer},
year = {2014},
language = {english}
}
@inproceedings{durand-lose13cie,
doi = {10.1007/978-3-642-39053-1_12},
hal = {https://hal.science/hal-00807227},
pdf = {Publications/2013_CiE.pdf},
slides = {Publications/2013_CiE_slides.pdf},
url_conf = {http://cie2013.disco.unimib.it/},
funding = {ANR project AGAPE},
note = {Invited talk for special session \emph{Computation in nature}},
editor = {Bonizzoni, Paola and Brattka, Vasco and L{\"o}we, Benedikt},
pages = {108--119},
number = {7921},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {CiE~2013, The Nature of Computation},
title = {Irrationality is needed to compute with signal machines with only three speeds},
publisher = {Springer},
series = {LNCS},
year = {2013},
language = {english},
abstract = {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.},
keywords = {Accumulation; Computability; Fractal; Mo del of
computation; Signal machine; Turing machine;
Unconventional computation}
}
@misc{durand-lose13frac,
hal = {https://hal.science/hal-00809143},
slides = {Publications/2013_FRAC_slides.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
howpublished = {FRAC d'hivers, Montpellier},
title = {Irrationality is needed to compute with signal machines with only three speeds},
month = feb # {28},
year = {2013},
language = {english}
}
@article{durand-lose13ijuc-nwc,
hal = {https://hal.science/hal-00989258},
title = {Special issue on {N}ew {W}orlds of {C}omputation ({NWC}~2011)},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
publisher = {Old {C}ity {P}ublishing},
journal = {Int J~Unconventional Computing},
volume = {9},
number = {1--2},
pages = {1--201},
year = {2013},
language = {english}
}
@misc{bergounioux+schang+maurel+savary+durand-lose+parmentier12,
hal = {https://hal.science/hal-00662507},
title = {{L'ordinateur et les langues}},
author = {Bergounioux, Gabriel and Schang, Emmanuel and Maurel, Denis and Savary, Agata and Durand-Lose, J{\'e}r{\^o}me and Parmentier, Yannick},
note = {Covalences 82 (2012)},
pages = {14-15},
year = {2012},
month = jan,
keywords = {M{\'e}diatisation; Linguistique},
language = {french}
}
@article{durand-lose+margenstern12ijgcs,
doi = {10.1142/S012905411202008X},
hal = {https://hal.science/hal-00806285},
author = {Margenstern, Maurice and Durand-Lose, J{\'e}r{\^o}me and Sutner, Klaus},
title = {Special issue on {F}rontier between Decidability and Undecidability and Related Problems},
journal = {Int. J. of Foundations of Computer Science},
year = {2012},
volume = {23},
number = {7},
pages = {1419-1522},
language = {english}
}
@article{durand-lose12nc-uc,
doi = {10.1007/s11047-012-9335-8},
hal = {https://hal.science/hal-00691466},
funding = {ANR project AGAPE},
pdf = {Publications/2012_NC_UC.pdf},
pages = {609--622},
number = {4},
volume = {11},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation~7\string: Geometrical accumulations and computably enumerable real numbers},
journal = {Nat Comput},
note = {Special issue on Unconv. Comp.~2011},
year = {2012},
language = {english},
abstract = {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.\par Colored line segments (traces of
signals) are drawn according to rules\string:
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.\par Starting with rational
numbers for coordinates and speeds, the time of any
isolated accumulation is a c.e.-$\mathbb{R}$
(\emph{computably enumerable}) real number. There is
a signal machine and an initial configuration that
accumulates at any c.e.-$\mathbb{R}$ time.
Similarly, the spatial positions of isolated
accumulations are exactly the d.-c.e.-$\mathbb{R}$
(\emph{difference of computably enumerable})
numbers. Moreover, there is a signal machine that
can accumulate at any c.e.-$\mathbb{R}$ time or
d.-c.e.-$\mathbb{R}$ position depending only on the
initial configuration.\par These existence results
rely on a two-level construction\string: an inner
structure simulates a Turing machine that output
orders to the outer structure which handles the
accumulation.},
keywords = {Abstract geometrical computations; Computable analysis;
Geometrical accumulations; c.e. and d.-c.e. real
numbers; Signal machine}
}
@misc{durand-lose12jourCal,
hal = {https://hal.science/hal-00691474},
pdf = {Exposes/2012-03-06_J_Calculabilite.pdf},
url_conf = {http://calculabilite.fr/index.html},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Signal machines{\string:} localization of isolated accumulation},
howpublished = {Journ{\'e}es Calculabilit{\'e}s, U. Paris 7},
month = mar # {5 and 6,},
year = {2012},
language = {english},
abstract = {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.}
}
@inproceedings{duchier+durand-lose+senot12tamc,
doi = {10.1007/978-3-642-29952-0_42},
arxiv = {http://arxiv.org/abs/1105.3454},
hal = {https://hal.science/hal-00673603},
hal_pw = {yya##8},
pdf = {Publications/2012_TAMC.pdf},
selection = {40 ∕ 86 = 47 \%},
funding = {ANR project AGAPE},
editor = {Agrawal, Manindra and Cooper, Barry S. and Li, Angsheng},
pages = {435--447},
number = {7287},
author = {Duchier, Denys and Durand-Lose, J{\'e}r{\^o}me and Senot, Maxime},
booktitle = {Theory and Applications of Models of Computations (TAMC~2012)},
title = {Computing in the fractal cloud\string: modular generic solvers
for {SAT} and {Q-SAT} variants},
publisher = {Springer},
series = {LNCS},
year = {2012},
language = {english},
abstract = {Abstract geometrical computation can solve hard
combinatorial problems efficiently\string: 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\string: 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.},
keywords = {Abstract geometrical computation; Signal machine;
Fractal; Satisfiability problems; Massive
parallelism; Model of computation}
}
@article{durand-lose12ijuc-uc-hypercomp,
hal = {https://hal.science/hal-00511224},
pdf = {Publications/2012_IJUC_UC_HC.pdf},
url_conf = {http://hypercomputation.net/hypernet10},
funding = {ANR project AGAPE},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Stannett, Mike},
pages = {33--46},
title = {Abstract geometrical computation~6\string: a reversible, conservative and rational based model for black hole computation},
journal = {Int J~Unconventional Computing},
volume = {8},
number = {1},
year = {2012},
publisher = {Old {C}ity {P}ublishing},
language = {english},
abstract = {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.\par 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.},
keywords = {Abstract geometrical computation; Black hole model;
Energy conservation; Reversibility; Signal machine}
}
@proceedings{durand-lose+jonoska12ucnc,
doi = {10.1007/978-3-642-32894-7},
hal = {https://hal.science/hal-00735493},
url_conf = {http://www.univ-orleans.fr/lifo/events/UCNC2012/},
title = {{U}nconventional {C}omputation and {N}atural {C}omputation ({UCNC}~2012)},
year = {2012},
publisher = {Springer},
series = {LNCS},
editor = {Durand-Lose, J{\'e}r{\^o}me and Jonoska, Nata\v{s}a},
number = {7445},
language = {english}
}
@incollection{adamatzky+durand-lose12hnc,
doi = {10.1007/978-3-540-92910-9_58},
hal = {https://hal.science/hal-00461197},
pdf = {Publications/2012_hnc.pdf},
author = {Adamatzky, Andrew and Durand-Lose, J{\'e}r{\^o}me},
title = {Collision Computing},
chapter = {58},
pages = {1949--1978},
booktitle = {Handbook of Natural Computing, Section VII\string: Broader Perspective --- Alternative Models of Computation},
publisher = {Springer},
year = {2012},
editor = {Corne, David},
language = {english},
abstract = {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.},
keywords = {Belousov-Zhabotinsky; Cellular automata; Collision
computing; Cycle tag systems; Geometrical
computation; Gliders; Localizations; Turing
machines}
}
@article{durand-lose11ijuc-nwc,
hal = {https://hal.science/hal-00749919},
title = {Special issue on {N}ew {W}orlds of {C}omputation ({NWC}~2009)},
year = {2011},
publisher = {Old {C}ity {P}ublishing},
journal = {Int J~Unconventional Computing},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
volume = {7},
number = {4},
pages = {221-311},
language = {english}
}
@unpublished{durand-lose11copcom,
hal = {https://hal.science/hal-00636376},
slides = {Publications/2011-10-19_COPCOM_slides.pdf},
url_conf = {http://www.complexity2011.org/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Introducing fractal computation},
year = {2011},
note = {Lecture at Coping with complexity (COPCOM~2011), 19, 20 oct., Cluj, Roumanie},
language = {english},
abstract = {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\string: abstract geometrical
computation where space and time are continuous and
can be effectively subdivided ad libidum; which we
introduce.},
keywords = {Fractal parallelism; SAT; unconventional computation;
abstract geometrical computation; signal machines}
}
@misc{duchier+durand-lose+senot11nwc,
hal = {https://hal.science/hal-00749867},
slides = {http://www.univ-orleans.fr/lifo/evenements/NWC2011/slides/NWC_2011_SENOT_slides.pdf},
url_conf = {http://www.univ-orleans.fr/lifo/evenements/NWC2011/},
author = {Duchier, Denys and Durand-Lose, J{\'e}r{\^o}me and Senot, Maxime},
title = {Computing with signals\string: a generic and modular signal machine for satisfiability problems},
howpublished = {Workshop New Worlds of Computation (NWC~2011), May 23--24, 2011},
year = {2011},
language = {english},
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.}
}
@misc{durand-lose+levorato+senot11lri,
hal = {https://hal.science/hal-00749838},
slides = {Publications/2011-05-03_W_Spacial_Computing_slides.pdf},
author = {Durand-Lose, J{\'e}r{\^o}me and Levorato, Vincent and Senot, Maxime},
title = {Machines {\`a} signaux\,: origine, puissance, retour au raisonnable},
howpublished = {Journ{\'e}e {S}pacial {C}omputing, LRI, Orsay},
month = may # {5},
year = {2011},
language = {french},
abstract = {L'expos{\'e} commencera par montrer la pr{\'e}sence et
l'utilisation de signaux dans les automates
cellulaires et le d{\'e}sir de s'affranchir de la
lourdeur du discret. Dans un second temps, nous
montrons la puissance du mod{\`e}le en montrant
comment r{\'e}soudre QSAT de fa{\c c}on
g{\'e}n{\'e}rique. Enfin dans un troisi{\`e}me
temps, nous essaierons de nous {\'e}loigner de
l'utopie d'un espace et d'un temps continus et
re-d{\'e}coupable ad infinitum en tentant de
discr{\'e}tiser automatiquement (grace {\`a} la
pr{\'e}-topologie).}
}
@inproceedings{duchier+durand-lose+senot11cie,
hal = {https://hal.science/hal-00605661},
pdf = {Publications/2011_CiE_booklet.pdf},
slides = {Publications/2011_CiE_slides.pdf},
url_conf = {http://cie2011.fmi.uni-sofia.bg/},
author = {Duchier, Denys and Durand-Lose, J{\'e}r{\^o}me and Senot, Maxime},
title = {Solving {Q-SAT} in bounded space and time by geometrical computation},
editor = {Ganchev, Hristo and L\"owe, Benedikt and Normann, Dag and Soskov, Ivan and Soskova, Mariya},
booktitle = {Models of computability in contecxt, 7th Int. Conf. Computability in Europe (CiE~2011) (abstracts and handout booklet)},
pages = {76--86},
publisher = {St. Kliment Ohridski University Press, Sofia University},
year = {2011},
language = {english},
abstract = {Abstract geometrical computation can solve
PSPACE-com\-plete problems efficiently\string: 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\string: an
exponential number of cases are explored
simultaneously by a massive parallelism.},
keywords = {Abstract geometrical computation; Signal machine; Q-SAT;
Fractal computation; Massive parallelism;
Unconventional computation}
}
@inproceedings{durand-lose11uc,
doi = {10.1007/978-3-642-21341-0_15},
hal = {https://hal.science/hal-00601746},
pdf = {Publications/2011_UC.pdf},
slides = {Publications/2011_UC_slides.pdf},
url_conf = {http://www.math.utu.fi/projects/uc2011},
selection = {17/33 51\%},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Calude, Cristian S. and Kari, Jarkko and Petre, Ion and Rozenberg, Grzegorz},
booktitle = {Int.{} Conf.{} Unconventional Computation 2011 (UC~2011)},
pages = {101--112},
title = {Geometrical accumulations and computably enumerable real numbers (extended abstract)},
publisher = {Springer},
series = {LNCS},
number = {6714},
year = {2011},
language = {english},
abstract = {Abstract geometrical computation involves drawing
colored line segments (traces of signals) according
to rules\string: 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.\par In the present paper, we show that
starting with rational numbers for coordinates and
speeds, the time of any accumulation is a {\it c.e.}
(\emph{computably enumerable}) real number and
moreover, there is a signal machine and an initial
configuration that accumulates at any {\it c.e.}
time. Similarly, we show that the spatial positions
of accumulations are exactly the {\it d-c.e.}
(\emph{difference of computably enumerable})
numbers. Moreover, there is a signal machine that
can accumulate at any {\it c.e.} time or {\it
d-c.e.} position.},
keywords = {Abstract geometrical computations; Computable analysis;
Geometrical accumulations; {\it c.e.} and {\it
d-c.e.} real numbers; Signal machine}
}
@article{durand-lose11tcs-wcsp,
doi = {10.1016/j.tcs.2010.07.013},
hal = {https://hal.science/hal-00504876},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract Geometrical Computation~4\string: Small {T}uring Universal Signal Machines},
year = {2011},
journal = {Theoret Comp Sci},
volume = {412},
pages = {57--67},
pdf = {Publications/2011_TCS_WCSP.pdf},
language = {english},
abstract = {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).},
keywords = {Abstract geometrical computation; cyclic tag systems;
Turing universality; signal machines; small
universal machines}
}
@article{durand-lose11nc-uc,
doi = {10.1007/s11047-010-9229-6},
hal = {https://hal.science/hal-00454605},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation~5\string: embedding computable analysis},
journal = {Nat Comput},
note = {Special issue on Unconv. Comp.~2009},
year = {2011},
pdf = {Publications/2011_NC_UC.pdf},
pages = {1261--1273},
number = {4},
volume = {10},
language = {english},
abstract = {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.\par
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.},
keywords = {Analog computation; Abstract geometrical computation;
Computable analysis; Signal machine; Type-2 Turing
machine}
}
@inproceedings{durand-lose10cie,
pdf = {Publications/2010_CiE_booklet.pdf},
slides = {Publications/2010_CiE_slides.pdf},
url_conf = {http://www.cie2010.uac.pt/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Ferreira, Fernando and Guerra, H{\'e}lia and Mayordomo, Elvira and Rasga, Jo{\~a}o},
booktitle = {Programs, Proofs, Processes, 6th Int. Conf. Computability in Europe (CiE~2010) (abstracts and extended abstracts of unpublished papers)},
note = {Contains a flaw, corrected in \cite{durand-lose11uc}},
pages = {158--167},
title = {The coordinates of isolated accumulations [includes] computable real numbers},
publisher = {CMATI, U. Azores},
year = {2010},
language = {english},
abstract = {\emph{This paper has a flaw. Please look at the
corrected version: \cite{durand-lose11uc} J\'er\^ome
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.}\par 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.\par 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.},
keywords = {Abstract geometrical computations; Accumulations;
Computable analysis; Computable number; Signal
machine}
}
@inproceedings{durand-lose10uc-work-hypercomp,
pdf = {Publications/2010_UC_WorkHC.pdf},
slides = {Publications/2010_UC_WorkHC_slides.pdf},
url_conf = {http://hypercomputation.net/hypernet10},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Stannett, Mike},
pages = {48--59},
title = {A reversible and conservative model based on rational signal machines for Black hole computation},
booktitle = {HyperNet 10\string: The Unconventional Computation 2010 (UC~202010) Hypercomputation Workshop},
year = {2010},
language = {english},
abstract = {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.\par 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.},
keywords = {Abstract geometrical computation; Black hole model;
Energy conservation; Reversibility; Signal machine}
}
@inproceedings{duchier+durand-lose+senot10isaac,
doi = {10.1007/978-3-642-17517-6_26},
pdf = {Publications/2010_ISAAC_full.pdf},
url_conf = {http://tclab.kaist.ac.kr/~isaac10},
author = {Duchier, Denys
and Durand-Lose, J{\'e}r{\^o}me
and Senot, Maxime},
editor = {Otfried, Cheong
and Chwa, Kyung-Yong
and Park, Kunsoo},
booktitle = {Int. Symp. on Algorithms and Computation (ISAAC~2010)},
pages = {279--290},
title = {Fractal Parallelism\string: Solving {SAT} in bounded space and time},
publisher = {Springer},
series = {LNCS},
number = {6506},
year = {2010},
language = {english},
abstract = {Abstract geometrical computation can solve NP-complete
problems efficiently\string: 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\string: 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.},
keywords = {Abstract geometrical computation; Signal machine;
Fractal; SAT; Massive parallelism; Model of
computation}
}
@misc{duchier+durand-lose+senot10jirc09,
hal = {https://hal.science/hal-00454603},
slides = {Exposes/2009_JIRC_slides.pdf},
url_conf = {http://www.info.univ-tours.fr/jirc2009/},
author = {Duchier, Denys and Durand-Lose, J{\'e}r{\^o}me and Senot, Maxime},
title = {Construction g\'eom\'etrique pour r\'esoudre \textbf{SAT} en temps constant},
howpublished = {Journ{\'e}e Informatique R{\'e}gion Centre (JIRC~2009), 22 janvier 2010},
year = {2010},
language = {french}
}
@inproceedings{duchier+durand-lose+senot10scw,
hal = {https://hal.science/hal-00511958},
hal_pw = {&0jc6l1},
pdf = {Publications/2010_SCW.pdf},
url_conf = {http://www.informatik.uni-giessen.de/ncma2010/},
title = {{M}assively {P}arallel {A}utomata in {E}uclidean {S}pace-{T}ime},
author = {{D}uchier, {D}enys
and {D}urand-{L}ose, {J}{\'e}r{\^o}me
and {S}enot, {M}axime},
affiliation = {{L}aboratoire d'{I}nformatique {F}ondamentale d'{O}rl{\'e}ans - {LIFO} - {U}niversit{\'e} d'{O}rl{\'e}ans: {EA}4022 - {E}cole {N}ationale {S}up{\'e}rieure d'{I}ng{\'e}nieurs de {B}ourges},
booktitle = {{F}irst {I}nternational {W}orkshop on {S}patial {C}omputing ({SCW} '10), a SASO~2010 satellite workshop},
address = {{B}udapest {H}ongrie},
audience = {internationale},
year = {2010},
language = {english},
abstract = {{I}n the cellular automata ({CA}) literature, discrete
lines in discrete space-time diagrams are often
idealized as {E}uclidean lines in order to design
{CA} or analyze their dynamic behavior. {I}n this
paper, we present a parallel model of computation
corresponding to this idealization\string:
dimensionless particles move uniformely at fixed
velocities along the real line and are transformed
when they collide. {L}ike {CA}, this model is
parallel, uniform in space-time and uses local
updating. {T}he 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.}
}
@incollection{durand-lose09ecss,
doi = {10.1007/978-0-387-30440-3_59},
hal = {https://hal.science/inria-00448437},
pdf = {Publications/2009_ECSS.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Cellular automata, {U}niversality of},
pages = {901--913},
booktitle = {Encyclopedia of Complexity and System Science},
publisher = {Springer},
year = {2009},
editor = {Meyers, Robert A. and Adamatzky, Andrew},
language = {english},
abstract = {Cellular automata (CA) and the subject are briefly
defined before two kinds of universality are
considered: computational universality and intrinsic
universality. A more involving section on advanced
topics ends this chapter.\par \emph{Computational
universality} deals with the capability to carry out
any computation as defined by Turing machines (in
computability Theory) while \emph{intrinsic
universality} deals with the capability to s imulate
any other machine of the same class (here cellular
automata). This distinction is fundamental here
because while computational universality refers to
finite inputs and relates to our understanding of
computing with computers, intrinsic universality
encompasses infinite co nfigurations and relates to
our understanding of the physical world. These
universalities are presented as simply as possible
and an example of universal CA is presented in each
case. The last section is devoted to the history
and advanced topics such as various definitions of
simulation between CA, restriction to reversible CA
and different underlying lattices.},
keywords = {Cellular automata; Turing universality; computational universality; intrinsic universality}
}
@article{durand-lose09nc,
doi = {10.1007/s11047-009-9117-0},
hal = {https://hal.science/hal-00447966},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation~3\string: black holes for classical and analog computing},
year = {2009},
journal = {Nat Comput},
volume = {8},
number = {3},
pages = {455-472},
pdf = {Publications/2009_Nat_Comp.pdf},
language = {english},
abstract = {The so-called Black Hole model of computation involves a
non Euclidean space-time where one device is
infinitely ``accelerated'' on one world-line but can
send some limited information to an observer working
at ``normal pace''. The keystone is that after a
finite duration, the observer has received the
information or knows that no information was ever
sent by the device which had an infinite time to
complete its computation. This allows to decide
semi-decidable problems and clearly falls out of
classical computability.\par A setting in a
continuous Euclidean space-time that mimics this is
presented. Not only is Zeno effect possible but it
is used to unleash the black hole power. Both
discrete (classical) computation and analog
computation (in the understanding of Blum, Shub and
Smale) are considered. Moreover, using nested
singularities (which are built), it is shown how to
decide higher levels of the corresponding
arithmetical hierarchies.}
}
@inproceedings{durand-lose09uc,
doi = {10.1007/978-3-642-03745-0_20},
hal = {https://hal.science/hal-00447965},
pdf = {Publications/2009_UC.pdf},
slides = {Publications/2009_UC_slides.pdf},
url_conf = {http://www.uc09.uac.pt/index.php},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Costa, Jos{\'e} F{\'e}lix and Dershowitz, Nachum},
booktitle = {Int{.} Conf{.} on Unconventional Computation 2009 (UC~2009)},
pages = {158--167},
title = {Abstract Geometrical Computation and Computable Analysis},
publisher = {Springer},
series = {LNCS},
number = {5715},
year = {2009},
language = {english}
}
@article{durand-lose+margenstern09fi-mcu,
doi = {10.3233/FI-2009-0029},
hal = {https://hal.science/hal-00461203},
title = {Special issue on {M}achines, {C}omputations and {U}niversality ({MCU}~2007)},
year = {2009},
publisher = {IOS Press},
journal = {Fund Inf},
author = {Margenstern, Maurice and Durand-Lose, J{\'e}r{\^o}me},
volume = {91},
number = {1--2},
pages = {1--195},
language = {english}
}
@inproceedings{durand-lose08cie,
hal = {https://hal.science/hal-00448746},
pdf = {Publications/2008_CiE_booklet.pdf},
slides = {Publications/2008_CiE_slides.pdf},
url_conf = {http://www.cs.swan.ac.uk/cie08},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Beckmann, Arnold and Dimitracopoulos, Costas and L\"owe, Benedikt},
booktitle = {Logic and Theory of Algorithms, 4th Conf. Computability in Europe (CiE~2008) (abstracts and extended abstracts of unpublished papers)},
pages = {107--116},
title = {Abstract geometrical computation with accumulations\string: beyond the {B}lum, {S}hub and {S}male model},
publisher = {University of Athens},
year = {2008},
language = {english},
abstract = {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 \textit{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.\par 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.},
keywords = {Abstract geometrical computation; Accumulations;Analog
computation; BSS model; Signal machine}
}
@inproceedings{durand-lose08uc-work-pc,
hal = {https://hal.science/inria-00448440},
pdf = {Publications/2008_UC_WorkPC.pdf},
slides = {Publications/2008_UC_WorkPC_slides.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Black hole computation\string: implementation with signal machines},
booktitle = {International Workshop Physics and Computation, Wien, Austria, Agust 25-28},
pages = {136--158},
year = {2008},
editor = {Calude, C. S. and Costa, J. F.},
series = {Research Report CDMTCS-327},
language = {english}
}
@inproceedings{durand-lose08wcsp,
hal = {https://hal.science/inria-00448439},
pdf = {Publications/2008_WCSP.pdf},
slides = {Publications/2008_WCSP_slides.pdf},
url_conf = {http://www.bcri.ucc.ie/SITES/CSP08/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Small {T}uring Universal Signal Machines},
publisher = {Cork University Press},
booktitle = {International Workshop on the Complexity of Simple Programs, Cork, Ireland, December 6-7},
year = {2008},
pages = {89--102},
editor = {Neary, Turlough and Seda, Anthony and Woods, Damien},
language = {english}
}
@inproceedings{durand-lose08jac,
hal = {https://hal.science/hal-00274005},
pdf = {Publications/2008_JAC.pdf},
slides = {Publications/2008_JAC_slides.pdf},
url_conf = {http://www.lif.univ-mrs.fr/jac/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Durand, Bruno},
booktitle = {Journ{\'e}es Automates cellulaires ({JAC~2008})},
pages = {238--249},
title = {The signal point of view\string: from cellular automata to signal machines},
year = {2008},
language = {english}
}
@inproceedings{durand-lose07cie,
doi = {10.1007/978-3-540-73001-9_25},
hal = {https://hal.science/hal-00144173},
pdf = {Publications/2007_CiE.pdf},
slides = {Publications/2007_CiE_slides.pdf},
url_conf = {http://www.amsta.leeds.ac.uk/~pmt6sbc/cie07.html},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Cooper, Barry S. and L\"owe, Benedikt. and Sorbi, Andrea},
booktitle = {Computation and Logic in the Real World, 3rd Conf. Computability in Europe (CiE 2007)},
number = {4497},
pages = {238--247},
publisher = {Springer},
series = {LNCS},
title = {Abstract geometrical computation and the linear {B}lum, {S}hub and {S}male model},
year = {2007},
language = {english},
abstract = {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 $\mathbb{R}$ (considered here as a
$\mathbb{R}$ unlimited register machine) by performing
algebraic computations.\par 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.},
keywords = {Abstract geometrical computation; Analog computation;
BSS model; Signal machine}
}
@proceedings{durand-lose+margenstern07mcu,
doi = {10.1007/978-3-540-74593-8},
hal = {https://hal.science/inria-00448750},
url_conf = {http://www.univ-orleans.fr/lifo/evenements/MCU07/},
title = {Machines, {C}omputations and {U}niversality ({MCU}~2007)},
year = {2007},
publisher = {Springer},
series = {LNCS},
editor = {Durand-Lose, J{\'e}r{\^o}me and Margenstern, Maurice},
number = {4664},
language = {english}
}
@inproceedings{durand-lose06tamc,
doi = {10.1007/11750321_61},
hal = {https://hal.science/hal-00079692},
pdf = {Publications/2006_TAMC.pdf},
slides = {Publications/2006_TAMC_slides.pdf},
url_conf = {http://gcl.iscas.ac.cn/accl06/TAMC06_Home.htm},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Cai, J.-Y. and Cooper, Barry S. and Li, Angshen},
booktitle = {Theory and Applications of Models of Computations (TAMC~2006)},
number = {3959},
pages = {644--653},
publisher = {Springer},
series = {LNCS},
title = {Forcasting black holes in abstract geometrical computation is highly unpredictable},
year = {2006},
language = {english},
abstract = {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\string: 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.\par We prove here that
forecasting an accumulation is $\Sigma^0_2$-complete
(in the arithmetical hierarchy) even if only energy
conserving signal machines are addressed (as in the
cited paper). The $\Sigma^0_2$-hardness is achieved
by reducing the problem of deciding whether a
recursive function (represented by a 2-counter
automaton) is strictly partial. The
$\Sigma^0_2$-membership is proved with a logical
characterization.},
keywords = {Abstract geometrical computation; Accumulation forecasting;
Arithmetical hierarchy; Black hole model; Energy
conservation; Super-Turing computation; Turing
universality; Zeno phenomena}
}
@inproceedings{durand-lose06cie,
doi = {10.1007/11780342_18},
hal = {https://hal.science/hal-00079687},
pdf = {Publications/2006_CiE.pdf},
slides = {Publications/2006_CiE_slides.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Beckmann, Arnold and Tucker, John V.},
booktitle = {Logical Approaches to Computational Barriers, 2nd Conf. Computability in Europe (CiE~2006)},
number = {3988},
pages = {163--172},
publisher = {Springer},
series = {LNCS},
title = {Reversible conservative rational abstract geometrical computation is {T}uring-universal},
year = {2006},
language = {english},
abstract = {In \textit{Abstract geometrical computation for black
hole computation (MCU~2004, 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.},
keyords = {Abstract geometrical computation; Conservativeness;
Rational numbers; Reversibility;
Turing-computability; 2-counter automata}
}
@article{durand-lose06fi-mcu,
hal = {https://hal.science/hal-00079720},
pdf = {Publications/2006_RR-LIFO_2005-5.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation~1\string: embedding Black hole computations with rational numbers},
journal = {Fund Inf},
year = {2006},
volume = {74},
number = {4},
pages = {491--510},
language = {english},
abstract = {The Black hole model of computation provides
super-Turing computing power since it offers the
possibility to decide in finite (observer's) time
any recursively enumerable (r.e.) problem. In this
paper, we provide a geometric model of computation,
\emph{conservative abstract geo\-metrical
computation}, that, although being based on rational
numbers (and not real numbers), has the same
property: it can simulate any Turing machine and can
decide any r.e. problem through the creation of an
accumulation. Finitely many signals can leave any
accumulation, and it can be known whether anything
leaves. This corresponds to a black hole effect.},
keywords = {Abstract geometrical computation; Black hole model;
Energy conservation; Malament-Hogarth space-time;
Super-Turing computation; Turing universality; Zeno
phenomena}
}
@inproceedings{durand-lose05mcu,
doi = {978-3-540-25261-0},
hal = {https://hal.science/hal-00079709},
pdf = {Publications/2004_MCU.pdf},
slides = {Publications/2004_MCU_slides.pdf},
url_conf = {http://lita.sciences.univ-metz.fr/~mcu2004/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {M. Margenstern},
booktitle = {Machines, Computations, and Universality (MCU~2004)},
number = {3354},
pages = {176--187},
publisher = {Springer},
series = {LNCS},
title = {Abstract geometrical computation for Black hole computation (extended abstract)},
year = {2005},
language = {english}
}
@inproceedings{durand-lose05cie,
doi = {10.1007/11494645_14},
hal = {https://hal.science/hal-00079815},
pdf = {Publications/2005_CiE.pdf},
slides = {Publications/2005_CiE_slides.pdf},
url_conf = {http://www.illc.uva.nl/CiE/CiE2005/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
editor = {Cooper, Barry S. and L{\"o}we, Benedikt and Torenvliet, Leen},
booktitle = {New Computational Paradigms, 1st Conf. Computability in Europe (CiE~2005)},
number = {3526},
pages = {106--116},
publisher = {Springer},
series = {LNCS},
title = {Abstract Geometrical Computation\string: {T}uring Computing Ability and Undecidability},
year = {2005},
language = {english}
}
@misc{durand-lose05jirc,
pdf = {Exposes/2005_JIRC_abstract.pdf},
slides = {Exposes/2005_JIRC_slides.pdf},
url_conf = {http://wcube.sir.blois.univ-tours.fr/jirc/},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Autostabilisation\,{:} de l'exclusion mutuelle sur un anneau {\`a} l'{\'e}lection d'un chef sur un graphe quelconque},
howpublished = {Journ{\'e}e Informatique R{\'e}gion Centre (JIRC~2005)},
month = jun # {29 and 30},
year = {2005},
language = {french}
}
@inproceedings{durand-lose05compCont,
slides = {Exposes/2005_WContinuum_Lisboa_slides.pdf},
url_conf = {http://math.isa.utl.pt/~mlc/continuum},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Abstract geometrical computation for Black hole computation},
booktitle = {Computations on the continuum, Lisboa, June 28-29 2005},
year = {2005},
language = {english}
}
@article{durand-lose04ipl,
doi = {10.1016/j.ipl.2003.11.010},
hal = {https://hal.science/hal-00079824},
pdf = {Publications/2004_IPL.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Inform Process Lett},
number = {5},
pages = {237--245},
title = {A {K}leene Theorem for Piecewise Constant Signals Automata},
volume = {89},
year = {2004},
language = {english},
abstract = {In this paper, we consider timed automata for piecewise
constant signals and prove that they recognize
exactly the languages denoted by signal regular
expressions with intersection and renaming. The main
differences from the usual timed automata are: time
elapses on transitions (passing through a state is
instantaneous), signals may be split on a run on an
automaton and constraints on transitions cor respond
to unions of open intervals but should be satisfied
on closed intervals. This makes exact rendez-vous
impossible. The paper stresses on the similarities
and differences from the usual model.},
keywords = {Timed automata; piecewise constant signal; signal
regular expression}
}
@article{alt+durand-lose04tocs,
hal = {https://hal.science/hal-00989260},
author = {Alt, Helmut and Durand-Lose, J{\'e}r{\^o}me},
title = {Special issue on {STACS} 2002},
journal = {Theory of Computing Systems},
volume = {37},
number = {1},
pages = {3--246},
year = {2004},
language = {english}
}
@phdthesis{durand-lose03hdr,
hal = {https://hal.science/tel-00548817},
pdf = {HDR/hdr.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Calculer g{\'e}om{\'e}triquement sur le plan --~machines {\`a} signaux},
school = {{\'E}cole Doctorale STIC, Universit{\'e} de Nice-Sophia Antipolis},
year = {2003},
type = {Habilitation {\`a} {D}iriger des {R}echerches},
note = {In French},
langid = {french},
language = {french},
abstract = {Ce m{\'e}moire se place dans l'{\'e}tude des
\emph{mod{\`e}les du calcul continus}. Nous y
montrons que la g{\'e}om{\'e}trie plane permet de
calculer. Nous d{\'e}finissons un calcul
g{\'e}om{\'e}trique et utilisons la continuit{\'e}
de l'espace et du temps pour stocker de
l'information au point de provoquer des
accumulations.\par Dans le monde des automates
cellulaires, on parle souvent de \emph{particules}
ou de \emph{signaux} (qui forment des lignes
discr{\`e}tes sur les diagrammes espace-temps) tant,
pour analyser une dynamique que, pour concevoir des
automates cellulaires particuliers. Le point de
d{\'e}part de nos travaux est d'envisager des
versions continues de ces signaux. Nous
d{\'e}finissons un mod{\`e}le de calcul continu, les
\emph{machines {\`a} signaux}, qui engendre des
figures g{\'e}om{\'e}triques suivant des r{\`e}gles
strictes. Ce mod{\`e}le peut se comprendre comme une
extension continue des automates cellulaires. Le
m{\'e}moire commence par une pr{\'e}sentation des
automates cellulaires et des particules. Nous
faisons ensuite une classification des
diff{\'e}rents mod{\`e}les de calcul existants et
mettons en valeur leurs aspects discrets et
continus. {\`A} notre connaissance, notre mod{\`e}le
est le seul {\`a} temps et espace continus mais
{\`a} valeurs et mises {\`a} jour discr{\`e}tes.\par
Dans la premi{\`e}re partie du m{\'e}moire, nous
pr{\'e}sentons ce mod{\`e}le, les machines {\`a}
signaux, et montrons comment y mener tout calcul au
sens de Turing (par la simulation de tout automate
{\`a} deux compteurs). Nous montrons comment
modifier une machine de mani{\`e}re {\`a}
r{\'e}aliser des transformations
g{\'e}om{\'e}triques (translations, homoth{\'e}ties)
sur les diagrammes engendr{\'e}s. Nous construisons
{\'e}galement les it{\'e}rations automatiques de ces
constructions de mani{\`e}re {\`a} contracter le
calcul {\`a} une bande (espace born{\'e}) puis,
{\`a} un triangle (temps {\'e}galement
born{\'e}).\par Dans la seconde partie du
m{\'e}moire, nous cherchons {\`a} caract{\'e}riser
les points d'accumulation. Nous reformulons de
mani{\`e}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{\'e}s
isol{\'e}es) et proposons un crit{\`e}re pour y
prolonger le calcul; mais le d{\'e}terminisme peut
{\^e}tre perdu dans le c{\^o}ne d'influence. Enfin,
en construisant pour tout automate {\`a} deux
compteurs une machine {\`a} signaux et une
configuration initiale simulant l'automate pour
toutes les valeurs possibles, nous montrons que le
probl{\`e}me de la pr{\'e}vision de l'apparition
d'une accumulation est $\Sigma^0_2$-complet.\par Le
m{\'e}moire se conclut par la pr{\'e}sentation de
nombreuses perspectives de recherches.},
keywords = {Automates cellulaires; g{\'e}om{\'e}trie; mod{\`e}le du
calcul continu; machine {\`a} signaux et signaux}
}
@inproceedings{durand-lose03exis,
pdf = {Exposes/2003_ETI.pdf},
url_conf = {http://perso.ens-lyon.fr/eric.thierry/ETI},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Geometric computation on the plane---signal machines},
booktitle = {Exystence Thematic Institute --- Discrete and Computational Aspects of Complex Systems, LIP, June 2003},
year = {2003},
language = {english}
}
@article{beauquier+durand-lose+gradinariu+johnen02jpdc,
doi = {10.1006/jpdc.2001.1832},
hal = {https://hal.science/hal-03277271},
pdf = {Publications/2002_JPDC.pdf},
author = {Beauquier, Joffroy and Durand-Lose, J{\'e}r{\^o}me and Gradinariu, Maria and Johnen, Colette},
journal = {Journal of Parallel and Distributed Computing},
title = {Token-based self-stabilizing uniform algorithms},
number = {5},
pages = {899--921},
volume = {62},
year = {2002},
language = {english},
abstract = {This work focuses on self-stabilizing algorithms for
mutual exclusion and leader election—two fundamental
tasks for distributed systems. Self-stabilizing
systems are able to recover by themselves, regaining
their consistency from any initial or intermediary
faulty configuration. The proposed algorithms are
designed for any directed, anonymous network and
stabilize under any distributed scheduler. The
keystones of the algorithms are the token management
and routing policies. In order to break the network
symmetry, randomization is used. The space
complexity is $O((D^++D^−)(log(snd(n))+2))$ where n is
the network size, snd(n) is the smallest integer
that does not divide n and $D^+$ and $D^−$ are the maximal
out and in degree, respectively. It should be noted
that snd(n) is constant on the average and equals 2
on odd-size networks.},
keywords = {self-stabilization; randomized protocol; unfair
scheduler; leader election; mutual exclusion;
directed network}
}
@incollection{durand-lose02book-bbm,
doi = {10.1007/978-1-4471-0129-1_6},
hal = {https://hal.science/hal-03277146},
pdf = {Publications/2002_BBM_book.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Computing inside the Billiard Ball Model},
pages = {135--160},
xxcrossref = {adamatzky02book},
booktitle = {Collision-based computing},
publisher = {Springer},
year = {2002},
editor = {Adamatzky, Andrew},
language = {english},
abstract = {The chapter studies relations between billiard ball
model, reversible cellular automata, conservative
and reversible logics and Turing machines. At first
we introduce block cellular automata and consider
the automata reversibility and simulation
dependencies between the block cellular automata and
classical cellular automata. We prove that there
exists a universal, i.e. simulating any Turing
machine, block cellular automaton with eleven
states, which is geometrically minimal. Basics of
the billiard ball model and presentation of an
information in the model are discussed then. We
demonstrate how to implement ball movement,
reflection of a signal, delays and cycles, collision
of signals in configurations of the cellular
automaton with Margolus neighborhood. Realizations
of Fredkin gate and NOT gate with dual signal
encoding are offered. The rest of the chapter deals
with a Turing and an intrinsic universality, and
uncomputable properties of the billiard ball
model. The Turing universality is proved via
simulation of a two-counter automaton, which itself
is Turing universal. We demonstrate that the
billiard ball model is intrinsically universal, or
complete, in a class of reversible cellular
automata, i.e. the model can simulate any reversible
automaton over finite or infinite configurations. A
novel notion of space-time simulation, that employs
whole space-time diagrams of automaton evolution, is
brought up. It is proved that the billiard ball
model is also able to space-time simulate any
(ir)reversible cellular automaton. Since the
billiard ball model possesses the Turing computation
power we can project a Turing machine’s halting
problem to development of cellular automaton
simulating the billiard ball model. Namely, we
uncover a connection between undecidability of
computation and high unpredictability of
configurations of the billiard ball model.},
keywords = {Cellular Automaton; Turing Machine; Cellular Automaton;
Register Unit; Fredkin Gate}
}
@misc{durand-lose02jssd,
slides = {http://deptinfo.unice.fr/~jdurand/Recherche/Exposes/2002_JSDD4.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Signaux libres},
howpublished = {4{\`e}mes Journ{\'e}es nationales Syst{\`e}mes Dynamiques Discrets},
month = jun,
year = {2002},
language = {french}
}
@inproceedings{durand-lose01dmccg,
hal = {https://hal.science/hal-04037638},
pdf = {Publications/2001_DMCCG.pdf},
slides = {Publications/2001_DMCCG_slides.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Representing Reversible Cellular Automata with Reversible
Block Cellular Automata},
editor = {Cori, Robert and Mazoyer, Jacques and Morvan, Michel and
Mosseri, R\'emy},
booktitle = {Discrete Models\string: Combinatorics, Computation, and
Geometry, DM-CCG~2001},
series = {Discrete Mathematics and Theoretical Computer Science
Proceedings},
year = 2001,
volume = {AA},
pages = {145--154},
language = {english},
abstract = {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 (\textit{Physica
D} 45) improved by Kari in 1996
(\textit{Mathematical System Theory} 29).},
keywords = {Cellular automata; reversibility; block cellular
automata; partitioning cellular automata}
}
@article{durand-lose01mlv,
doi = {None, juillet 2021},
hal = {https://hal.science/hal-03277181},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Multiple Valued Logic},
title = {Back to the universality of the {B}illiard ball model},
number = {5--6},
pages = {423--437},
volume = {6},
year = {2001},
pdf = {Publications/2001_MVL-BBM.pdf},
language = {english},
abstract = {A full construction of the universality of the Billiard
ball model, a lattice gas model introduced by
Margolus in 84 is provided. The BBM is a reversible
two-dimensional block cellular automaton with two
states. Fredkin's gate and reversible logic can be
emulated inside the Billiard ball model. They are
use to embed two-counter automata, a model universal
for computation.\par In the one-dimensional case,
there exists a universal block cellular automaton
with 11 states.}
}
@article{durand-lose00tcs,
doi = {10.1016/S0304-3975(99)00075-4},
hal = {https://hal.science/hal-03277188},
pdf = {Publications/durand-lose00tcs.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Theoret Comp Sci},
number = {1--2},
pages = {117--129},
title = {Reversible space-time simulation of cellular automata},
volume = {246},
year = {2000},
language = {english},
abstract = {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 \textit{et al.} in 1989.},
keywords = {Cellular Automata; Intrinsic universality; Partitioned
Cellular Automata; Space-time simulation;
Reversibility}
}
@article{durand-lose00ipl,
doi = {10.1016/S0020-0190(00)00056-9},
hal = {https://hal.science/hal-03277206},
pdf = {Publications/2000_IPL.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Inform Process Lett},
pages = {203-207},
title = {Randomized uniform self-stabilizing mutual exclusion},
volume = {74},
year = {2000},
language = {english},
abstract = {A system is \emph{self-stabilizing} if when started in
any configuration it reaches a legal configuration,
all subsequent configurations are legal. We present
a randomized self-stabilizing mutual exclusion that
works on any uniform graphs. It is based on
irregularities that have to be present in the graph.
Irregularities make random walks and merge on
meeting. The number of states is bounded by
$o(\delta\ln n)$ where $\delta$ is the
maximal degree and $n$ is the number of
vertices. The protocol is also proof against
addition and removal of processors.},
keywords = {Self-stabilization; Mutual exclusion; Fault
tolerance; Distributed computing; Random walks}
}
@article{durand-lose98tcs,
doi = {10.1016/S0304-3975(97)00073-X},
hal = {https://hal.science/hal-03277218},
pdf = {Publications/1996_RR-LaBRI_1148.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Theoret Comp Sci},
number = {1--2},
pages = {183--193},
title = {Parallel transient time of one-dimensional sand pile},
volume = {205},
year = {1998},
language = {english},
abstract = {Sand dripping in one-dimensional Sand Pile Model is
first studied. Patterns and signals appear. Their
behaviors and interactions are explained and
asymptotic approximations are made. The total
collapsing time of a single stack of sand is linear
in function of the number of grains.},
keywords = {Sand Pile Model; Dynamic systems; Stabilization; Parallelism}
}
@inproceedings{durand-lose98mcu,
pdf = {Publications/1998_MCU.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {Universal Machines and Computations (UMC~1998)},
editor = {M. Margenstern},
pages = {118--133},
publisher = {Universit\'e de {M}etz},
title = {About the Universality of the Billiard ball model},
volume = {2},
year = {1998},
language = {english}
}
@inproceedings{durand-lose98opodis,
pdf = {Publications/1998_OPODIS.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {Distributed computing (OPODIS~1998)},
editor = {A. Bui and V. Villain},
pages = {89--98},
publisher = {Hermes},
title = {Randomized uniform self-stabilization mutual exclusion},
year = {1998},
language = {english}
}
@inproceedings{durand-lose98jour-montoises,
address = {Mons (Belgique)},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {Journ\'es montoises},
editor = {V. Bruy\`ere},
month = mar,
title = {Cellular automata, block {CA}, partition {CA} reversibility and simulation},
year = {1998},
language = {english}
}
@misc{durand-lose98jmont,
pdf = {Exposes/1998_JourMont.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
title = {Automates cellulaires, r{\'e}versibilit{\'e} et universalit{\'e}},
howpublished = {Journ{\'e}es Montoises~1998},
year = {1998},
language = {french}
}
@inproceedings{durand-lose97stacs,
doi = {10.1007/BFb0023479},
hal = {https://hal.science/hal-01559642},
pdf = {Publications/1997_STACS.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {STACS 1997},
number = {1200},
pages = {439--450},
publisher = {Springer},
series = {LNCS},
title = {Intrinsic universality of a $1$-dimensional
reversible cellular automaton},
year = {1997},
language = {english},
abstract = {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.},
keywords = {Block Cellular Automata; Cellular Automata; Partitioned
Cellular Automata; Reversibility; Reversible
Cellular Automata; Intrinsic Universality}
}
@inproceedings{durand-lose97ca-workshop,
address = {Gargnano (Italie)},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {Cellular Automata Workshop 1997},
editors = {Stefania Bandini and T. Bezzi and G. Cattaneo and G. Mauri},
month = sep,
title = {Cellular automata, block {CA}, partitioned {CA}, reversibility and simulation},
year = {1997},
language = {english}
}
@phdthesis{durand-lose96phd,
hal = {https://hal.science/tel-00548830},
pdf = {http://www.univ-orleans.fr/lifo/Members/Jerome.Durand-Lose/Recherche/These/these_R-V.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
note = {In French},
school = {LaBRI},
title = {Automates Cellulaires, Automates \`a Partitions et Tas de Sable},
type = {Th{\`e}se de doctorat},
year = {1996},
langid = {french},
language = {french},
abstract = {Cette th{\`e}se s'int{\'e}resse dans un premier temps
aux automates cellulaires r{\'e}versibles, et dans
un second temps aux tas de sable lin{\'e}aires.\par
Nous construisons diverses simulations reliant les
automates cellulaires aux automates {\`a}
partitions, en particulier celle des automates
cellulaires r{\'e}versibles par les automates {\`a}
partitions r{\'e}versibles, ce qui {\'e}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 {\`a} partitions r{\'e}versibles
de dimension 2. En rassemblant ces r{\'e}sultats,
nous montrons qu'il existe des automates cellulaires
r{\'e}versibles capables de simuler tous les
automates cellulaires r{\'e}versibles de m{\^e}me
dimension.\par Dans un espace lin{\'e}aire, Tas de
sable et Chip firing game sont {\'e}quivalents. Nous
portons notre attention sur le cas o{\`u} les grains
tombent un {\`a} un. Des motifs d{\'e}limit{\'e}s
par des signaux apparaissent au sein des
configurations engendr{\'e}es. Nous {\'e}tudions la
dynamique du syst{\`e}me et d{\'e}montrons un
{\'e}quivalent asymptotique. Nous {\'e}tendons nos
m{\'e}thodes et nos r{\'e}sultats {\`a} d'autres
types de configurations initiales. Dans chaque cas
{\'e}tudi{\'e}, le temps parall{\`e}le est
inf{\'e}rieur au temps s{\'e}quentiel dans un
rapport de l'ordre du nombre de piles mises en \oe
uvre.},
keywords = {Automates Cellulaires; Automates {\`a} Partitions;
R{\'e}versibilit{\'e}, Simulation; Tas de Sable
Lin{\'e}aires; Chip Firing Game; Billiard Ball
Model}
}
@article{durand-lose96cs,
hal = {https://hal.science/hal-03277267},
pdf = {Publications/1997_RR-LaBRI_1157.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
journal = {Complex Systems},
pages = {195--206},
number = {3},
title = {Grain sorting in the one dimensional sand pile model},
volume = {10},
year = {1996},
language = {english},
abstract = {We study the evolution of a one-dimensional pile, empty
at first, which receives a grain in its first stack
at each iteration. The final position of grains is
singular: grains are sorted according to their
parity. They are sorted on trapezoidal areas
alternating on both sides of a diagonal line of
slope $\sqrt{2}$. This is explained and proved by
means of a local study. Each generated pile, encoded
in height differences, is the concatenation of four
patterns: $22$, $1313$, $0202$, and $11$. The
relative length of the first two patterns and the
last two patterns converges to $\sqrt{2}$. We make
asymptotic expansions and prove that all the lengths
of the pile are increasing proportionally to the
square root of the number of iterations.},
keywords = {Sand Pile Model; Dynamic systems; Stabilization}
}
@inproceedings{durand-lose96ca-workshop,
address = {Schlo{\ss} Rauischholzhauen},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {Cellular Automata Workshop~1996},
editors = {M. Kutrib and T. Worsch},
month = mar,
pages = {14--16},
title = {Sand Dripping in Linear Space},
year = {1996},
language = {english}
}
@misc{durand-lose96ami-nice,
pdf = {Exposes/1996_GDR-PRC.NICE.pdf},
addreess = {Nice},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
organizer = {I. Litowsky and B. Martin},
title = {Simulation Espace-Temps R\'eversible d'Automates Cellulaires Non-R\'eversibles},
month = sep,
year = {1996},
howpublished = {{\'E}cole d'automne du {GRD-PRC AMI}, Nice},
language = {french}
}
@techreport{durand-lose96rr-labri-1135,
pdf = {Publications/1996_RR-LaBRI_1135.pdf},
aaanotezzz = {submitted to Mathematical System Theory so long ago ;-)},
type = {Research Report},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
institution = {LaBRI},
number = {1135-96},
title = {Any Reversible Cellular Automaton Can be Represented with Block Permutations},
year = {1996},
language = {english}
}
@techreport{durand-lose96rr-labri-96-1113,
pdf = {Papier/1996_RR-LaBRI_1113.pdf},
type = {Research Report},
address = {Universit\'e Bordeaux~I, 33\,405 {Talence} Cedex, {France}},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
institution = {LaBRI},
number = {1113--96},
title = {Sand Piles in Digraphs},
year = {1996},
language = {english}
}
@misc{durand-lose98mosydis,
author = {Durand-{L}ose, J{\'e}r{\^o}me},
howpublished = {Rencontre Mosydis (GdR-PrC AMI), {\'ENS} {C}achan},
organizer = {Petit, Antoine},
month = nov,
title = {Universalit\'e intrins\`eque au sein des Automates cellulaires partitionn\'es r\'eversibles},
year = {1996},
language = {french}
}
@inproceedings{durand-lose95latin,
doi = {10.1007/3-540-59175-3_92},
hal = {https://hal.science/hal-01559493},
pdf = {Publications/1995_LATIN.pdf},
author = {Durand-{L}ose, J{\'e}r{\^o}me},
booktitle = {LATIN 1995},
editors = {Baeza-Yates, Ricardo and Goles, Eric and Poblete, P.},
number = {911},
pages = {230--244},
publisher = {Springer},
series = {LNCS},
title = {Reversible cellular automaton able to simulate
any other reversible one using
partitioning automata},
year = {1995},
language = {english},
abstract = {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.},
keywords = {Block Cellular Automata; Cellular Automata; Partitioned
Cellular Automata; Intrinsic Universality;
Reversibility; Reversible Cellular Automata}
}
@inproceedings{daumas+durand-lose+tock94,
author = {Daumas, Marc and Durand-Lose, J{\'e}r{\^o}me and Tock, Louis-Pascal},
booktitle = {XIV Int.\ Conf.\ of the Chilean Computer Science Society},
editors = {C. Isaac and R. Peralta},
pages = {283-294},
title = {High Speed Implementation of a Cellular Automaton},
year = {1994},
pdf = {Publications/1996_RT-LIP_1996-01.pdf},
language = {english}
}